题解：CF2089B2 Canteen (Hard Version)

题目很快就切了，全靠 tag 打的好。
做不出题怪大脑，胡出来题自称佬。

注意到答案上界为

n

所以暴力模拟的操作次数为

n ^ 2

次，不可接受。注意到对于每次操作的

a_i

和

b_i

其中必然有一个会清零，对于为零的值我们的操作实际上没有意义，所以我们本质上有意义的操作只有

n

次。

考虑如何模拟过程中只模拟有意义操作，注意到可以用一个单调队列维护当前位置以及前面的

a

。对于一个位置

i

，要么

b_i

清零，要么单调队列清空，操作次数只有

n

次，可以接受。

那有人就要问了，这只是 easy 版的做法，那 hard 版呢？莫慌莫慌，听我徐徐道来。我们可以二分答案，用上面的方法检验答案是否合法。这样时间复杂度为

O(n \log n)

，可以通过。

code

CPP

#include<bits/stdc++.h>
using namespace std;
#define N 200005
int n, a[N], b[N];
long long k;
inline bool check(int x) {
	int aa[N], bb[N];
	long long ret = 0;
	deque<int> q;
	for(int i = n; i; --i) 
		aa[i] = a[i], bb[i] = b[i];
	for(int i = 1; i <= n; ++i) {
		q.push_back(i);
		while(!q.empty() && i - q.front() + 1 > x) 
			ret += aa[q.front()], q.pop_front();
		if(ret > k) return 0;
		while(!q.empty() && bb[i] >= aa[q.back()]) 
			bb[i] -= aa[q.back()], q.pop_back();
		if(!q.empty()) 
			aa[q.back()] -= bb[i], bb[i] = 0;
	}
	for(int i = 1; !q.empty() && i <= n; ++i) {
		while(!q.empty() && n - q.front() + i + 1 > x) 
			ret += aa[q.front()], q.pop_front();
		if(ret > k) return 0;
		while(!q.empty() && bb[i] >= aa[q.back()]) 
			bb[i] -= aa[q.back()], q.pop_back();
		if(!q.empty()) 
			aa[q.back()] -= bb[i], bb[i] = 0;
	}
	return 1;
}
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	int t;
	cin >> t;
	while(t--) {
		cin >> n >> k;
		for(int i = 1; i <= n; ++i) cin >> a[i];
		for(int i = 1; i <= n; ++i) cin >> b[i];
		int l = 0, r = n;
		while(l <= r) {
			int mid = l + r >> 1;
			if(check(mid)) r = mid - 1;
			else l = mid + 1;
		}
		printf("%d\n", r + 1);
	}
	return 0;
}

题解：CF2089B2 Canteen (Hard Version)

文章操作

code

相关推荐

评论

题解：CF2089B2 Canteen (Hard Version)