【Gym - 101234J】Zero Game【单调队列】

题意：

       给定一串01串，m次询问，每次询问给你一个数k。k为对于这个01串所能进行的最多次操作，每次操作可以将该串中任意一个位置的数移到任意一个其他的位置。

       每次询问之后，输出在这个操作数之内，所能达到的最长的连续0的长度。

 

思路：

       一开始考虑的是尺取法进行求解，然后和队友一起debug了一整场...宣告凉凉...

       我和队友的思路是如果遇到1，就把它移掉；然后对于该状态，再用剩余可操作数来更新ans，看上去好像是个好想法，但是仔细去想的话，就会发现这是不可行的。

       例如，你现在尺取的长度是L...x...y...R，[L,R] 这个区间，但是最优解却是在 [x,y] 这个区间，那你就取不到这个区间了。由此尺取法就错了。

       还是对于尺取的核心理解的不透彻，尺取法要求你尺取时左右端点右移的指标是一个单调性的指标，而本题中显然指标不单调，由此尺取不可行。

 

       既然尺取不可行，那么我们就需要重新来看看这个序列了。

       由于这是一个01串，很自然地可以想到记录前缀和来记录区间内一共有多少个1的问题，由此我们记录给每一个点都记录一个前缀和。

       那么对于区间 [L+1，R] ，本题的结果是什么呢？可以发现本题的结果应该是【K次操作】

              ans = R-(L+1)+1-(sum[R]-sum[L])+K-(sum[R]-sum[L])

       化简后，可以得到

              ans = (R-2*sum[R])-(L-2*sum[L])+K

       由此，我们对于每一个点都维护一个a[i] = ans，然后用单调队列进行更新即可。

 

       还记得单调队列吗，维护一个单调递增的单调队列就是对于当前要扔进来的i值，判断队尾元素是否大于等于这个值，假如大于等于这个值，就执行r--的操作，直到队尾元素比这个值小的时候，执行 q[++r] = i 操作，即将当前这个值扔到队尾。

       然后再判断队首元素和队尾元素之间间隔的0的个数，如果间隔的0的个数大于K，则 l++，直到队首元素和队尾元素之间间隔的0的个数小于K为止。

       然后往队列中添加元素，就更新一遍 ans 的答案，即可求出正解。

 

反思：

还是没有站在题意本身进行思考，以及对于尺取的本质掌握的不够深入，才导致对于算法判断错误，从而最终也没搞出这道题。

 

代码：

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define rep(i,a,b) for(int i = a;i <= b;i++)
using namespace std;
const int N = 1e6+1000;

char s[N];
int m,n;
int a[N];
int sum[N];
int q[N];
int cnt;

void solve(int k)
{
	int ans = 0;
	q[1] = 0;
	int l = 1, r = 1;
	rep(i,1,n)
	{	
		while(l <= r && a[q[r]] >= a[i]) r--;
		q[++r] = i;
		while(l <= r && sum[i]-sum[q[l]] > k) l++;
		ans = max(ans,a[q[r]]-a[q[l]]+k);
	}
	printf("%d\n",min(ans,cnt));
}

int main()
{
	while(~scanf("%s",s))
	{
		cnt = 0;
		scanf("%d",&m);
		int len = strlen(s);
		n = len;
		sum[0] = 0;a[0]=0;
		rep(i,1,len)
		{
			if(s[i-1] == '0'){
				sum[i] = sum[i-1];
				cnt++;
			} 
			else sum[i] = sum[i-1]+1;
			a[i] = i-2*sum[i];

		}
		rep(i,1,m)
		{	
			int x;
			scanf("%d",&x);
			solve(x);
		}
	}
	return 0;
}