【题目描述】 农夫约翰有N(1<=N<=100000)个牛舍，它们之间由小路连成了一个圈。约翰还有N头奶牛，但是她们并不十分听话，散乱的站在这N个牛舍里，于是有些牛舍挤爆了，而有些牛舍一头牛也没有。约翰不希望看到这种情况，就命令这些奶牛不允许同时挤在一个牛舍里，一个牛舍里只许有一头牛。于是奶牛们按照顺时针方向开始转移。但是她们并不能跑的很轻松，经过k个牛舍的疲惫值为k的平方。约翰要知道，达到一个牛舍里只有一头牛的情况至少需要的疲劳值总和。 【输入格式】 第一行一个整数N，既表示牛舍的个数也表示奶牛的头数。 接下来N行，每行一个整数ai表示第i个牛舍的奶牛数，保证所有ai的和等于N 【输出格式】 最小的疲劳值总和 【样例输入】 10 1 0 0 2 0 0 1 2 2 2 【样例输出】 33 【分析】 首先明确一点：每一头奶牛走的路都不能重复。 如上图，设A牛舍有2头奶牛，B牛舍有1头奶牛。 显然最优解是2——B牛舍给C牛舍一头牛，A牛舍再给B牛舍1头牛，而不是A牛舍出一头牛直达C牛舍。 为了不使路径重复，我们可以逆时针将每头奶牛移到尽量远的地方，这样相当于顺时针将奶牛移到尽量近的地方，且避免了路径的重复。 下一步破环为链。显然，一定存在至少一头奶牛不会移动。如果每一头奶牛都移动了且最后每个牛舍只有一头牛，说明原来的顺序已经满足每个牛舍只有一头牛了。因为牛只能顺时针移动，不能跑回去。 设a[i]表示第i头奶牛原来的牛舍序号，可以使a[i]-i最大的奶牛待在原位不动，然后其他的奶牛依次排放即可。
var a,b:array[0..100001]of longint; i,n,p,x,s,ans:longint; begin read(n); for i:=1 to n do begin read(x); for p:=1 to x do begin inc(s);a[s]:=i; end; end; s:=0; for i:=1 to n do if a[i]-i>s then begin s:=a[i]-i;p:=i; end; b[p]:=a[p]; for i:=p-1 downto 1 do b[i]:=b[i+1]-1; for i:=p+1 to n do b[i]:=b[i-1]+1; for i:=1 to n do ans:=ans+sqr(b[i]-a[i]); write(ans); end.转载于:https://www.cnblogs.com/JRX2015U43/p/6533486.html
相关资源：JAVA上百实例源码以及开源项目