气死我了...这个毒瘤内存分配.....
优先队列 + 链表模拟，看起来搞一搞就好了却WA来WA去...
最后对拍手动找才发现错误：
erase的时候不要急急忙忙插入wait！要把同一时期的erase完再插入wait！
#include <cstdio>
#include <queue>
typedef long long LL;
const LL N = ;
const LL INF = 1ll << ; struct Ask {
LL time, len, last;
Ask(LL t, LL l, LL s) {
time = t;
len = l;
last = s;
}
}; struct Out {
LL time, pos;
Out(LL t, LL p) {
time = t;
pos = p;
}
inline bool operator <(const Out &x) const {
return time > x.time;
}
}; struct ListNode {
LL pre, nex, l, r;
bool vis;
}li[N]; LL head = N - , tail = N - , top = ; LL n;
std::queue<Ask> Wait, Come;
std::priority_queue<Out> Erase; inline void init() {
li[head].nex = ;
li[].pre = head;
li[].nex = tail;
li[].l = ;
li[].r = n - ;
li[tail].pre = ;
return;
} inline LL getpos(LL k) {
LL p = li[head].nex;
while(p != tail) {
while(li[p].vis) {
p = li[p].nex;
}
if(p == tail) {
return ;
}
if(li[p].r - li[p].l + >= k) {
return p;
}
p = li[p].nex;
}
return ;
} inline LL insert(Ask x) {
LL p = getpos(x.len);
if(!p) {
return ;
}
if(li[p].r - li[p].l + == x.len) {
li[p].vis = ;
return p;
}
++top;
li[top].r = li[p].r;
li[top].l = li[p].l + x.len;
li[p].r = li[top].l - ;
li[p].vis = ;
li[top].nex = li[p].nex;
li[top].pre = p;
li[p].nex = top;
li[li[top].nex].pre = top;
return p;
} inline void erase(Out x) {
LL p = x.pos;
li[p].vis = ; /// b p c
LL b = li[p].pre, c = li[p].nex;
if((li[b].vis || b == head) && (li[c].vis || c == tail)) {
return;
}
if(li[b].vis || b == head) {
li[p].nex = li[c].nex;
li[li[c].nex].pre = p;
li[p].r = li[c].r;
return;
}
if(li[c].vis || c == tail) {
li[p].pre = li[b].pre;
li[li[b].pre].nex = p;
li[p].l = li[b].l;
return;
}
li[p].nex = li[c].nex;
li[p].pre = li[b].pre;
li[li[c].nex].pre = p;
li[li[b].pre].nex = p;
li[p].l = li[b].l;
li[p].r = li[c].r;
return;
} int main() {
LL t, len, last;
int c = , w = ;
scanf("%lld", &n);
init();
while() {
scanf("%lld%lld%lld", &t, &len, &last);
if(!t && !len && !last) {
break;
}
Come.push(Ask(t, len, last));
}
LL sum = , T = ;
while(!Wait.empty() || !Come.empty() || !Erase.empty()) {
LL tc = INF, te = INF;
if(!Come.empty()) {
tc = Come.front().time;
}
if(!Erase.empty()) {
te = Erase.top().time;
}
if(te <= tc) {
while(Erase.top().time == te) {
erase(Erase.top());
Erase.pop();
if(Erase.empty()) {
break;
}
}
T = te;
LL in = ;
while(!Wait.empty()) {
in = insert(Wait.front());
if(!in) {
break;
}
Erase.push(Out(te + Wait.front().last, in));
Wait.pop();
}
}
else {
LL in = insert(Come.front());
if(in) {
Erase.push(Out(tc + Come.front().last, in));
}
else {
Wait.push(Come.front());
sum++;
}
Come.pop();
}
} printf("%lld\n%lld", T, sum);
return ;
}
AC代码