关于数据
查看原帖
关于数据
1047694
Shq_likes_AC楼主2024/7/13 19:52

CSFBF的样例什么错误都查不出来!

#include<bits/stdc++.h>
using namespace std;
long long n, d, k,dp[1000000];
struct node {
	int a, b;
}a[1000000];
struct queue {
	int q[1000000];
	int tail, head;
	inline void ch() { if (head > tail)exit(1145141145); if (head < 0 || tail < 0 || head>999999 || tail>999999) exit(314159265); }
	inline void init() { head = 0, tail = 0; }
	inline void pub(int n) { q[++tail] = n; ch(); }
	inline void puf(int n) { q[head--] = n; ch(); }
	inline void pob() { --tail; ch(); }
	inline void pof() { head++; ch(); }
	inline void gte() { tail = head; }
	inline int f() { return q[head + 1]; }
	inline int b() { return q[tail]; }
	inline int s() { return tail - head; }
}q;
bool cmp(node a, node b)
{
	return a.a != b.a ? a.a<b.a : a.b>b.b;
}
bool check(int mid)
{
	q.init();
	memset(dp, 0x80, sizeof(dp));
	dp[0] = 0;
	int l = max(1ll, d - mid), r = d + mid;
	for (int i = 1, j = 0; i <= n; i++)
	{
		while (a[i].a - a[j].a >= l &&j<i)
		{
			if (dp[j] != 0x8080808080808080) 
			{
				while (q.s() && dp[q.f()] <= dp[j]) //这行错了
 				//while (q.s() && dp[q.b()] <= dp[j]) 正确代码
					q.pob();
				q.pub(j);
			}
			j++;
		}
		while (q.s() && a[q.f()].a + r < a[i].a)
			q.pof();
		if (q.s())
			dp[i] = dp[q.f()] + a[i].b;
		if (dp[i] >= k)
			return 0;
	}
	return 1;
}
int main()
{
	cin >> n >> d >> k;
	for (int i = 1; i <= n; i++)
		cin >> a[i].a >> a[i].b;
	sort(a + 1, a + n + 1, cmp);
	int l = 0, r = 1000000000;
	while (l <= r)
		if (check(l + r >> 1))
			l = (l + r >> 1) + 1;
		else
			r = (l + r >> 1) - 1;
	if (l == 1000000001)
		cout << -1;
	else
		if (!check(r))
			cout << r;
		else
			cout << l;
}//样例全过,能得70分
2024/7/13 19:52
加载中...