USACO 2016 February Contest Gold: T1 Circular Barn

题目大意

有一个

每一个点有 $d^2 的能量。$

请设计一种牛的走法，使得每一个点上都正好有一头牛，且最小化耗费的能量。

题目分析

观察题目，会发现总有一个点能作为起点1，使得在满足情况的条件下不会有牛从 N点再绕回到 1点。

我们可以对该数组扫描一遍找出这个起点，然后从起点开始往后扫，每到一个新的点就接上当前点的牛，并把之前带过来的一头牛放下，这样一定是最有情况。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 
 5 int n,c;
 6 inline ll Calc(ll x){
 7     return x*(x+1)*(2*x+1)/6;
 8 }
 9 int main(){
10     scanf("%d",&n);
11     vector<ll> a(n);
12     for(int i=0;i<n;++i){
13         scanf("%lld",&a[i]);
14         c=max(0ll,c+a[i]-1);
15         //cout<<i<<' '<<c<<endl;
16     }
17     
18     for(int i=0;;++i){
19         //cout<<i<<' '<<c<<endl;
20         if(!c){
21         //    puts("");
22         //    cout<<i<<endl;
23             rotate(a.begin(),a.begin()+i,a.begin()+n);
24             break;
25         }
26         c=max(0ll,c+a[i]-1);
27     }
28     //puts("");
29     //for(int i=0;i<n;++i)
30     //    cout<<a[i]<<' ';
31     //puts("");
32     ll res=0;
33     for(int i=0;i<n;++i){
34         res+=Calc(a[i]+c-1)-Calc(c-1);
35         //把带来的c-1头牛放完剩下的a[i]头牛要走的距离和，用平方和公式计算
36         //cout<<i<<' '<<c<<' '<<a[i]+c-1<<' '<<c-1<<endl;
37         c=max(0ll,c+a[i]-1);
38     }
39     printf("%lld
",res);
40     return 0;
41 }