P5942 敌对球迷 题解

· · 题解

题面

简要题意：在一个环形数列中选择连续的若干个数，使得【这些数的和】与【其他数的和】的最小值最大。

我们可以枚举我们选一串数的终点在哪里，显然，为了让这串数的和是答案，它的和不能超过数列总和的一半，同时我们要让这个和尽量大。所以我们要贪心的往前选择，这样就达到了 O(n^2) 的复杂度

如何优化呢？我们可以发现当终向后时，起点也一定是随着向后。所以我们当从一个终点转到下一个终点时，我们要判断现在总长是否超过要求，如果是，我们就贪心的把起点一位一位往后移动。

那么我们要怎样处理这个环呢？对于环上问题，我们最常用的方式就是把整段序列复制一次接到后面，这样我们就可以方便的处理经过 len_n 和 len_1 的区间了。

AC代码

#include<iostream>
using namespace std;
int len[1000000];
int sum=0;
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>len[i];sum+=len[i];
        len[i+n]=len[i];
    }
    int ans=0,maxl=sum/2+1;//答案，最大答案。 
    int now=0,qi=1;//当前长度，当前的起点 
    for(int i=1;i<=2*n;i++){
        now+=len[i];
        while(now>=maxl){
            now-=len[qi];qi++;      
        }
        ans=max(now,ans);
    }
    cout<<ans;
    return 0;
}