Producing Machines

[qiaobaaa]

include

include

include

using namespace std;

struct MyStruct { int id; int time; }machines[25000]; unordered_map<int, int>umap; int index; struct cmp { bool operator()(int a, int b)const { if (machines[a].time!=machines[b].time) { return machines[a].time > machines[b].time; } else { return machines[a].id > machines[b].id; } } }; set<int, cmp>sset;

void init(int N, int mId[], int mTime[]) { sset.clear(); umap.clear(); index = 0;

for (int i = 0; i < N; i++)
{
    index++;
    machines[index].id = mId[i];
    machines[index].time = mTime[i];

    umap[mId[i]] = index;
    sset.emplace(index);
    //index++;
}

}

int add(int mId, int mTime) { //找到 if (umap.count(mId)) { //先删除后更新 int idx = umap[mId]; sset.erase(idx); machines[idx].time = mTime; sset.emplace(idx); } //没找到 else { index++; machines[index].id = mId; machines[index].time = mTime; umap[mId] = index; sset.emplace(index); //index++; } return sset.size(); }

int remove(int K) { for (int i = 0; i < K; i++) { //sset.erase(sset.begin()); //**** umap.erase(machines[sset.begin()].id); sset.erase(sset.begin()); } return machines[sset.begin()].id; } //二分计算本题的核心所在

int binary(int l,int h,int M) { int low = l; int high = h; int middle, cnt; vectorcall; int ii=0; //** cnt = h; for (auto i = sset.begin(); i != sset.end(); i++) { call.push_back(machines[*i].time); ii++; }

while (low<=high)
{
    middle = (low + high) / 2;
    int tem = 0;
    for (int i = 0; i < ii; i++)
    {
        //**************
        tem = tem + (middle / call[i]);
    }
    if (tem>=M)
    {
        //*********************
        cnt = middle;
        high = middle - 1;
    }
    else
    {
        low = middle + 1;
    }
}
return cnt;

} int produce(int M) { int cnt = 0; int mintime = machines[sset.rbegin()].time; cnt = binary(0, M mintime, M); return cnt; }

[qiaobaaa]

vector set