bzoj 4412: [Usaco2016 Feb]Circular Barn

4412: [Usaco2016 Feb]Circular Barn

Description

有一个N个点的环，相邻两个点距离是1。点顺时针标号为1..N。
每一个点有ci头牛，保证∑ci=N。
每头牛都可以顺时针走。设一头牛走了d个单位停下了，将耗费d^2的能量。
请设计一种牛的走法，使得每一个点上都正好有一头牛，且最小化耗费的能量。

Input

第一行一个数N。N <= 100000
接下来N行，每行一个数ci。

Output

输出一个数表示耗费能量的最小值

Sample Input

10
1
0
0
2
0
0
1
2
2
2

Sample Output

题解：

所有奶牛只能往顺时针方向走，所以应该存在一个起点。

那么怎么找这个起点呢？？

先把所有权值-1，然后我们考虑这样一个问题，若从x->y之间所有的奶牛都不会走出这个范围当且仅当不存在一个k，使得k->y权值为正，这个脑补一下吧。。。

那么这个起点就是这个环的最大子串和的起点，证明不讲了，然后就把环变成一条链，终点就是起点前一个。

最后是求最小值，这个也是有难度的。

由于(x+y)²>x²+y²

所以到某个点肯定会在中途换班，具体实现用个队列就好了。

#include<stdio.h>

#include<iostream>

using namespace std;

const int N=;

int n,i,s,l,x,t,w,a[N],g[N];

long long ans;

int main()

{

    scanf("%d",&n);

    for(i=;i<=n;i++)

    {

        scanf("%d",&a[i]);

        a[n+i]=a[i];

    }

    ans=;x=;

    for(i=;i<=*n-;i++)

    {

        if(s<) s=,x=i;

        s+=a[i]-;

        if(s>ans)

        {

            ans=s;

            l=x;

        }

    }

    t=;w=;ans=;

    for(i=l;i<=l+n-;i++)

    {

        while(a[i]--) g[++w]=i;

        ans+=1LL*(i-g[t])*(i-g[t]);

        t++;

    }

    cout<<ans;

    return ;

}

巴特西