[COCI2010-2011#5] DVONIZ

A_Sunny_Day · 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 就可以通过递推得到每个位置作为起点时的答案。

递推式为：

ans[i]=\max(ans[i-1]-2,ans[i]) (1\le i \le n)

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

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

K=\min(R-mid,mid-l+1)

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

ans[mid-K+1]=2\times 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;
}