是道硬菜,按照题目意思,我们需要用到set来保存当前的任务的起始下标和占用长度,小根堆来保证我们每次取出的都是时间最近的任务,用队列来存储需要等待的任务,每次读进来先free一下当前的内存,如果check成功我们就可以执行任务,如果不行就放到等待队列里,然后每次free的时候取出堆顶,如果符合当前的时刻就要把它取出并删掉,同时更新一下最后时刻final,检查一下当前等待队列的队头能不能取出还有需要处理边界等细节要特别注意
C++ 代码
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<set>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
const int N=1e5+10,INF=2e8;
int final, cnt,t,m,p,n;//final是最终时刻
set<PII> st;//存一下下标和占用长度
priority_queue<PII, vector<PII>, greater<PII>> heap;//处理一下最先释放的内存,记录时间和下标
queue<PII> que;//等待队列,存一下占用长度和时间
bool check(int t,int m,int p)
{
for (auto it = st.begin(); it != st.end();it++)
{
auto tt = it;
tt++;
if(tt!=st.end())
{
if(m<=tt->first-(it->first+it->second-1)-1)
{
int pos = it->first + it->second;
st.insert({pos, m});
heap.push({t + p, pos});
return 1;
}
}
}
return 0;
}
void free(int t)//释放内存
{
while(heap.size()&&heap.top().first<=t)//如果小于当前的时刻
{
int now = heap.top().first;
while(heap.size()&&heap.top().first==final)//如果到时刻了就要释放
{
auto t = heap.top();
heap.pop();
auto it = st.lower_bound({t.second, 0});//把堆和set里的都删掉
st.erase(it);
}
final = now;//更新一下最后时刻
while(que.size())
{
if(check(now,que.front().first,que.front().second))//如果能插入就插入
{
que.pop();
}
else
break;
}
}
}
int main()
{
scanf("%d", &n);
st.insert({-1, 1}), st.insert({n, 1});//处理边界
while(~scanf("%d%d%d",&t,&m,&p))
{
if(t==0&&m==0&&p==0)
break;
free(t);
if(!check(t,m,p))
{
que.push({m, p});
cnt++;//累加等待队列的任务
}
}
free(INF);//把所有任务都完成
printf("%d\n%d\n",final,cnt);
return 0;
}