题解 P2381 【圆圆舞蹈】

· · 题解 

/*

Tips:
1.首先找到与第一头牛最远的牛的位置,即找到一个牛(pos)与1号牛的距离>=周长的一半  
2.接着记录  pos之前的这头牛(pos-1)
3.显然pos这头牛到第一头牛的逆时针顺序是最大的,(pos-1)这头牛到第一头牛的顺时针距离是最大的  
4.那我们在这二者之间取个最大值
5.接下来不断向前推进,第一头牛变为第二头牛,更新pos和(pos-1)到第二头牛的距离,再更新一下答案即可. 
6.如果我们向前推进奶牛的时候,pos到当前推进到的奶牛的顺时针距离<周长的一半,那我们就向前推进pos即可 

*/

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#define Mi return
#define manchi 0

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 100000 +5 ;

inline int read()
{
    int num=0,w=1;char ch=getchar();
    while(ch<'0' || ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch<='9' && ch>='0')
        num=(num<<1)+(num<<3)+ch-'0',ch=getchar();
    Mi num*w;
}

int n,a[N],sum,ans;

int main()
{
//  freopen("circle.in","r",stdin);
//    freopen("circle.out","w",stdout);
    n=read();
    for(register int i=1;i<=n;i++)
        a[i]=read(),sum+=a[i];//i-1 -> i 

    int half_over=0,pos=0;
    for(register int i=1;i<=n;i++)
    {
        half_over+=a[i-1];//找到第一个超过一半周长的 
        if(half_over>sum/2){pos=i;break;}//记录此时位置 
    }
    int way=abs(sum-half_over);
    int way_=half_over-a[pos-1];  
    ans=max(way,way_); 
    for(int i=1;i<=n;i++)
    {
        half_over-=a[i-1];//向前推进奶牛 
        while(half_over<=sum/2)
        {
            half_over+=a[pos+1];//要是pos不符合条件,那就向前推进pos 
            pos++;
        }
        //更新答案 
        ans=max(ans,min(half_over,abs(sum-half_over))); 
        ans=max(ans,min(half_over-a[pos-1],abs(sum-(half_over-a[pos-1]))));
    }
    printf("%d",ans);
    Mi manchi;
}
//2019-07-26 typed by zbwer 
//题目地址:https://www.luogu.org/problem/P2381