Untitled

 avatar
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