题目描述

Being a fan of contemporary architecture, Farmer John has built a new barn in the shape of a perfect circle. Inside, the barn consists of a ring of n rooms, numbered clockwise from 1…n around the perimeter of the barn (3≤n≤1000). Each room has doors to its two neighboring rooms, and also a door opening to the exterior of the barn.
Farmer John owns n cows, and he wants exactly one cow to end up in each room in the barn. However, the cows, being slightly confused, line up at haphazard doors, with possibly multiple cows lining up at the same door. Precisely ci cows line up outside the door to room i, so ∑ci=n.
To manage the process of herding the cows so that one cow ends up in each room, Farmer John wants to use the following approach: each cow enters at the door at which she initially lined up, then walks clockwise through the rooms until she reaches a suitable destination. Given that a cow walking through d doors consumes d2 energy, please determine the minimum amount of energy needed to distribute the cows so one ends up in each room.

输入描述:

The first line of input contains n. Each of the remaining n lines contain c1…cn.

输出描述:

Please write out the minimum amount of energy consumed by the cows.

示例1

输入
10
1
0
0
2
0
0
1
2
2
2
输出
33

解答

【题目描述】：
有一个个点的环，相邻两个点距离是1。点顺时针标号为。
每一个点有头牛，保证。
每头牛都可以顺时针走。设一头牛走了个单位停下了，将耗费的能量。
请设计一种牛的走法，使得每一个点上都正好有一头牛，且最小化耗费的能量。
【题目解法】：
我们考虑枚举环的起点，这样所有的奶牛都只能往右边走
然后考虑一个奶牛，他在i，要走到j，在之间还有一个位置的奶牛没有走过
显然，因此我们先，然后换一个奶牛，这样最优
因此我们从后往前枚举，如果一个点的奶牛数量为1，显然合法跳过，如果>1显然该起点不合法
如果为0，我们从前面最近的地方拉一条奶牛过来即可，复杂度
然后总的复杂度
题目没有范围。一开始一位这一定是水题，然后就TLE了
我们考虑事实上对于某个起点开始的序列可能不合法
考虑前缀和对任意i成立合法
我们将原数组两倍之后枚举起点i，对于中任意一个点j都要满足
也就是，右边和无关，因此我们求的的区间最小值即可
维护一个线段树，判断是否合法，实际上合法的情况很少
然后就飞快的跑过去了TAT 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N=200005;
const long long INF=1e15;
struct node {int mint;} tree[N*4];
int n,m; long long ans,a[N],b[N],sum[N],nowans;
inline long long getint()
{
    long long x=0; char c=getchar(); bool flag=false;
    while ((c!='-')&&((c<'0')||(c>'9'))) c=getchar();
    if (c=='-') flag=true,c=getchar();
    while ((c>='0')&&(c<='9')) x=x*10+(long long)(c-'0'),c=getchar();
    if (flag) return -x; else return x;
}
void init()
{
    n=getint(); m=n+n; ans=INF;
    for (int i=1; i<=n; i++) b[i]=b[n+i]=getint();
    for (int i=1; i<=m; i++) sum[i]=sum[i-1]+b[i];
}
void build(int p,int l,int r)
{
    if (l==r) {tree[p].mint=sum[l]-l; return;}
    int mid=(l+r)/2; build(p*2,l,mid); build(p*2+1,mid+1,r);
    tree[p].mint=min(tree[p*2].mint,tree[p*2+1].mint);
}
int ask(int p,int l,int r,int ll,int rr)
{
    if ((l==ll)&&(r==rr)) return tree[p].mint;
    int mid=(l+r)/2;
    if (rr<=mid) return ask(p*2,l,mid,ll,rr);
    else if (ll>mid) return ask(p*2+1,mid+1,r,ll,rr);
    else return min(ask(p*2,l,mid,ll,mid),ask(p*2+1,mid+1,r,mid+1,rr));
}
long long calc()
{
    if (a[1]==0) return INF; long long far=0;
    for (int i=1; i<=n; i++) if (a[i]>0) far=i;
    if (far==0) return 0; long long nowans=0;
    for (int i=n; i>=1; i--)
    {
        if (a[i]>1) return INF; if (a[i]==1) continue;
        if (far>=i)
        {
            far=i-1;
            for (;(far>0)&&(a[far]==0);far--);
        }
        if (a[far]==0) return INF;
        a[i]++; nowans=nowans+(long long)(far-i)*(far-i);
        if (nowans>=ans) return nowans;
        a[far]--; for (;(far>0)&&(a[far]==0);far--);
    }
    return nowans;
}
void solve()
{
    int cnt=0;
    for (int i=1; i<=n; i++)
    {
        int nowans=ask(1,1,m,i,n+i-1);
        if (nowans<sum[i-1]-(i-1)) continue;
        for (int j=1; j<=n; j++) a[j]=b[i+j-1];
        ans=min(ans,calc());
    }
    printf("%lld\n",ans); //I64d->lld
}
int main()
{
    init();
    build(1,1,m);
    solve();
    return 0;
}

来源：zhouzixuan的博客