题目描述

略

样例

略

C++ 代码

#include <bits/stdc++.h>
using namespace std;

typedef pair<int,int> PII;
int n,cnt,t,m,p,ans;//ans:finish time,cnt:num of all enter waiting lists
queue<PII> waits;//first:mem len, second: occupied time len
set<PII> runs; //first:start idx,second: mem len
priority_queue<PII,vector<PII>,greater<PII>> endts;//release time,startidx;

bool give(int t,int m, int p) {
    for(auto it=runs.begin(); it!=runs.end();) {
        int start=it->first+it->second;
        if(++it==runs.end())break;
        if(m>it->first-start)continue;
        runs.insert({start,m});
        endts.push({t+p,start});
        return true;
    }
    return false;
}

void finish(int t) {
    while(endts.size()&&endts.top().first<=t) {
        auto top=endts.top();
        int f=top.first;
        endts.pop();
        auto it=runs.lower_bound({top.second,0});
        runs.erase(it);
        if(endts.size()&&endts.top().first==f)continue;
        ans=f;
        while(waits.size()) {
            auto front=waits.front();
            if(!give(f,front.first,front.second)) break;
            waits.pop();
        }
    }
}

int main(){
    cin>>n;
    runs.insert({-1,1}),runs.insert({n,1});
    while(cin>>t>>m>>p,t||m||p) {
        finish(t);
        if(give(t,m,p))continue;
        waits.push({m,p});
        cnt++;
    }
    finish(2e9);
    cout<<ans<<endl<<cnt<<endl;
    return 0;
}