Untitled
unknown
plain_text
6 months ago
2.4 kB
3
Indexable
#include <set> #include <algorithm> #include <vector> #include <queue> using namespace std; struct Taxi { int id; int x; int y; int mMoveDistance; int mRideDistance; bool operator<(const Taxi& other) const { if (mRideDistance == other.mRideDistance) return id < other.id; return mRideDistance > other.mRideDistance; } }; Taxi taxi[2001]; struct Result { int mX, mY; int mMoveDistance; int mRideDistance; } result[2001]; set<Taxi> best; int topID[5]; int n, m, l, cnt; int getDis(int x1, int x2, int y1, int y2) { return abs(x1 - x2) + abs(y1 - y2); } void init(int N, int M, int L, int mXs[], int mYs[]) { n = N; m = M; l = L; cnt = 1; best.clear(); for (int i = 0; i < m; i++) { Taxi tax = { cnt, mXs[i], mYs[i], 0, 0 }; taxi[cnt] = tax; best.insert(taxi[cnt]); cnt++; } } int pickup(int mSX, int mSY, int mEX, int mEY) { int bestID = -1; int bestDis = 999999; for (int i = 1; i <= m; i++) { int x1 = taxi[i].x; int y1 = taxi[i].y; int disCur = getDis(x1, mSX, y1, mSY); if (disCur < bestDis && disCur <= l) { bestDis = disCur; bestID = i; } } if (bestID == -1) return -1; // Remove and reinsert to maintain correct ordering in `best` best.erase(taxi[bestID]); // Update taxi's move and ride distances, position taxi[bestID].mMoveDistance += bestDis + getDis(mSX, mEX, mSY, mEY); taxi[bestID].mRideDistance += getDis(mSX, mEX, mSY, mEY); taxi[bestID].x = mEX; taxi[bestID].y = mEY; // Reinsert the modified taxi to maintain set ordering best.insert(taxi[bestID]); return bestID; } Result reset(int mNo) { Result res; res.mX = taxi[mNo].x; res.mY = taxi[mNo].y; res.mMoveDistance = taxi[mNo].mMoveDistance; res.mRideDistance = taxi[mNo].mRideDistance; // Remove the taxi from `best`, reset values, and reinsert to maintain order best.erase(taxi[mNo]); taxi[mNo].mMoveDistance = 0; taxi[mNo].mRideDistance = 0; best.insert(taxi[mNo]); return res; } void getBest(int mNos[]) { auto it = best.begin(); for (int i = 0; i < 5 && it != best.end(); i++, it++) { mNos[i] = it->id; } }
Editor is loading...
Leave a Comment