P7635 [COCI2010-2011#5] DVONIZ 题解

· · 题解

思路解析：

1.考虑暴力算法 O(n^3)。

枚举左右端点，遍历判断是否合法。最多只能拿 N \le 200 的分数。

2.暴力加上前缀和优化 O(n^2)。

可以省去遍历所需复杂度。能拿到 N \le 5 \times 10^3 的分数。

3.枚举中间点加二分答案 O(nlogn)。

因为题目中说每个元素的值都为正整数。 可以考虑枚举中间点 mid，因而从 mid 左右出发的元素加和是单调递增的。可以考虑运用二分答案，求出以 mid 为中点的左右最远扩展程度（最远到达 l,r 点），取较短的一边，即为此时 mid 的最长长度。

即

len=min(r-mid,mid-l+1);
tot[mid-len+1]=max(2*len,tot[mid-len+1]);

注：mid 为左区间最后一个元素的下标。

但这样的做法是不完全的，有部分端点的值被更新到了，但是有一些端点没有被更新。考虑到将一个合法的区间去掉头尾两个元素，还是成立的，可以推出:

tot[i]=max(tot[i],tot[i-1]-2);

最后这里要更新一边才能得到最终答案。 这样的做法可以拿到 N \le 10^5 的分数。

4.枚举中间点加尺取法 O(n)。

形同第三条，也是枚举 mid 时找出最远到达的两点 l,r，但是发现在 mid 往右移动的时候 l,r 两点也在往右移动，所以可以使用尺取法优化掉二分答案的复杂度。当 mid 右移后，若左区间的累加和已经大于 S，将左端点向右移动，直到左区间累加和小于等于 S。若右区间累加和小于 S，且右区间还能加入元素，那么将右端点向右移动，扩大右区间长度。因为 l,r 最多经历每个端点一次，所以整体的时间复杂度是 O(n) 的。可以通过 N \le 3 \times 10^6 的数据。不要忘记第三条中说的最后更新哦。

code:

#include<bits/stdc++.h>
#define N 3000005
using namespace std;
int n,k;
int a[N],s[N],tot[N];
int main()
{
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    int len,head=1,tail=1;
    for(int mid=1;mid<=n;mid++)
    {
        while(s[mid]-s[head-1] > k)  head++;
        while(s[tail+1]-s[mid] <= k && tail < n) tail++;
        len=min(tail - mid , mid - head + 1);
        tot[mid-len+1]=max(tot[mid-len+1],len*2);
    }
    for(int i=1;i<=n;i++)
        tot[i]=max(tot[i],tot[i-1]-2);
    for(int i=1;i<=n;i++)
        printf("%d\n",tot[i]);
    return 0;
}