WA40,第一个答案错误,悬关
查看原帖
WA40,第一个答案错误,悬关
515891
paper_楼主2024/1/23 21:25

不清楚最后一个 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:尝试放入当前块,若不可,将其放入等待队列
*/
2024/1/23 21:25
加载中...