[BZOJ 4412] [Usaco2016 Feb]Circular Barn

注意到“牛隻能順時針走“，是以貪心一定是對的。

把環複制成鍊，一遍掃找到最優位置，兩遍掃算出答案。

沒了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
inline void read(int &x){x=;char c;while((c=getchar())<'0'||c>'9');for(x=c-'0';(c=getchar())>='0'&&c<='9';x=x*+c-'0');}
const int N =  ;

int a[N + N], sum[N + N], n, pos = ;

int main()
{
    read(n);
    for (int i = ; i <= n; ++i) 
        read(a[i]), a[n + i] = a[i];

    for (int i = ; i <= n + n; ++i)
    {
        if (i == pos + n) break;
        sum[i] = sum[i - ] + a[i] - ;
        while (sum[i] < sum[pos - ]) pos++;
    }

    LL ans = ; 
    int l = pos + n - , r = pos + n - ;

    while (r >= pos)
    {
        while (!a[l]) l--;
        ans += (LL) (r - l) * (r - l);
        a[l]--, r--;
    }

    printf("%lld\n", ans);
    return ;
}