自动搬运

查看原文

来自洛谷，原作者为

	A_Sunny_Day 路漫漫其修远兮，吾将上下而求索

搬运于2025-08-24 22:31:45，当前版本为作者最后更新于2021-06-26 18:35:56，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

[COCI2010-2011#5] DVONIZ

题意：

​ 定义长度为 $2\times K$ 并且前 $K$ 个元素之和不超过 $S$ 且后 $K$ 各元素之和也不超过 $S$ 的数列为 INTERESTING 串，给定长度为 $N$ 的数列 $A$ ，对于每个元素，求出以该元素为起点的最长 INTERESTING 串。($2 \le N \le 100000,1\le S \le 2\times10^9$)

​ 首先我们定义 $\text{mid}$ 为一个 INTERESTING 串的中心：即分界点。设 $\text{L}$,$\text{R}$ 分别为这个串的左端点和右端点，而这个串长度为 $2\times K$ 我们把 $\text{L}$ ~ $\text{mid}$ 这一段看作串的前 $K$ 个。而 $\text{mid}$ ~ $\text{R}$ 这一段看作为串的后 $K$ 个。显然，当 $\text{mid}$ 不变时所有以 $\text{mid}$ 为中心点的且长度小于 $K$ 的串都是 INTERESTING 串。所以，我们只要找到对于每一个位置作为 $\text{mid}$ 时所能取到的最长的长度 $K$ 就可以通过递推得到每个位置作为起点时的答案。

​ 递推式为：

​ 那么问题变成了求对于每个位置作为 $\text{mid}$ 时所能取到的最大的 $K$。 我们考虑从左到右枚举 $\text{mid}$。 注意到，当 $\text{mid}$ 向右移动时，它能取到最远的左端点和右端点$L,R$ 必定也会向右边移动。那么我们就可以用双指针（尺取）的方法来解决这个问题。时间复杂度为 $O(n)$。

​ 在取完之后，我们根据左右指针所在的位置 $L,R$ 来得到此时能取到的最大的 $K$。 即：

​ 而更新答案我们这样更新：

​ 在结束后我们再遍历一遍，通过上文得到的递推式推出所有的 $\text{ans}$ 值。

代码如下：

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5+5;
int n;
ll s,a[MAXN],len[MAXN];
int main()
{
	scanf("%d %lld",&n,&s);
	for(int i=1;i<=n;++i)
		scanf("%lld",&a[i]);
	int l=1,r=0;
	ll ls=0,rs=0;
	while(rs+a[r+1]<s&&r<n) rs+=a[++r];
	for(int i=1;i<=n;++i)
	{
		ls+=a[i];
		rs-=a[i];
		while(ls>s&&l<=i)
		{
			ls-=a[l];
			++l;
		}
		while(rs+a[r+1]<=s&&r<n) rs+=a[++r];
		int le=min(i-l+1,r-i);
		if(le>0) len[i-le+1]=le*2;
	}
	for(int i=1;i<n;++i) len[i]=max(len[i-1]-2,len[i]);
	for(int i=1;i<n;++i)
		printf("%lld\n",len[i]);
	printf("0\n");
	return 0;
}