「题解」P6496 [COCI2016-2017#2] Nizin

Wenoide · 2020-05-10 20:18:43 · 题解

重复下述步骤：

• 若最左端元素较最右端元素更小，则合并最左端的两个元素。
• 若最右端元素较最左端元素更小，则合并最右端的两个元素。
• 若两端的元素相等，则对除两端的元素外的其他元素重复以上步骤。

显然，回文数组两端的元素应相等。

第一种情况下，迟早需要合并最左端的两个元素。否则最右端的元素会越来越大，直到数组中只剩一个元素。

第二种情况同理。

第三种情况下，两端的元素已经回文，可以不作处理。

时间复杂度 O(n)。

参考代码：

#include<cstdio>
const int MAXN=1000000+10;
long long p[MAXN];
int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;++i){
        scanf("%lld",&p[i]);
    }
    int l=1,r=n,cnt=0;
    while(l<r){
        if(p[l]>p[r]){
            --r;
            p[r]+=p[r+1];
            ++cnt;
        }
        else if(p[l]<p[r]){
            ++l;
            p[l]+=p[l-1];
            ++cnt;
        }
        else{
            ++l,--r;
        }
    }
    printf("%d",cnt);
    return 0;
}