不清楚最后一个 while 循环处理时的时间添加方式,等待队列莫名其妙会变空。
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int N = 20010;
inline int read() {
int x = 0, w = 1;
char ch = 0;
while (ch < '0' || ch > '9') {
if (ch == '-') w = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9') {
x = x * 10 + (ch - '0');
ch = getchar();
}
return x * w;
}
struct P {
int s, t, f; // 起始地址,块的长度,是否为空
int l, r;
}p[N];
priority_queue<PII, vector<PII>, greater<PII> > q1;
queue<PII> q2;
int n, idx, ans1, ans2;
void add(int k, int u) {
p[u].r = p[k].r;
p[p[k].r].l = u;
p[k].r = u;
p[u].l = k;
}
void D(int k) {
p[p[k].r].l = p[k].l;
p[p[k].l].r = p[k].r;
}
bool work(int s, int len, int t) {
int la = 0;
for (int i = p[0].r; i != N - 1 && i; i = p[i].r) {
if (!p[i].f && p[i].t >= len) {
if (p[i].t == len) {
p[i].f = 1;
q1.push({t + s, i});
}
else {
int u = ++ idx;
p[u].s = p[i].s, p[u].t = len, p[u].f = 1;
p[i].s += len, p[i].t -= len;
add(la, u);
q1.push({t + s, u});
}
return true;
}
la = i;
}
return false;
}
void merge() {
for (int i = p[0].r; i != N - 1 && i; i = p[i].r) {
if (!p[i].f && !p[p[i].r].f) {
p[i].t += p[p[i].r].t;
D(p[i].r);
}
}
}
signed main() {
freopen("1.in", "r", stdin);
int TIME = 0;
n = read();
p[0] = {0, 0, 1, 0, N - 2};
p[N - 1] = {n + 1, 0, 1, N - 2, 0};
p[N - 2] = {0, n, 0, 0, N - 1};
while (1) {
TIME ++;
int a = read(), b = read(), c = read(); //申请时刻、长度、时间。
if (!a && !b && !c) break;
while (q1.size() && q1.top().first <= a) {
int T = -1;
if (q1.size()) T = q1.top().first;
while (q1.size() && q1.top().first == T) {
int u = q1.top().second;
p[u].f = 0;
q1.pop();
}
merge();
while (T != -1 && q2.size() && work(T, q2.front().first, q2.front().second)) q2.pop();
}
merge();
if (!work(a, b, c)) q2.push({b, c}), ans2 ++;
ans1 = max(ans1, a);
}
while (q2.size()) {
int T = -1;
if (q1.size()) T = q1.top().first;
while (q1.size() && q1.top().first == T) {
int u = q1.top().second;
p[u].f = 0;
q1.pop();
}
merge();
if (T != -1) while (q2.size() && work(T, q2.front().first, q2.front().second))
ans1 = max(ans1, T + q2.front().second), q2.pop();
else if (q2.size() && work(ans1, q2.front().first, q2.front().second))
ans1 += q2.front().second, q2.pop();
}
while (q1.size()) ans1 = max(ans1, q1.top().first), q1.pop();
cout << ans1 << '\n' << ans2;
return 0;
}
/*
1:将到时间的块弹出
2:合并空时间块
3:检查当前是否有可以等待队列中的可放入的
4:尝试放入当前块,若不可,将其放入等待队列
*/