【bzoj4412】[Usaco2016 Feb]Circular Barn

先看成一条链

for一遍找位置

在for一遍算答案

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstring>
 4 #include<string>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 typedef long long LL;
10 
11 #define N 100010
12 
13 int n;
14 int cnt=1;
15 
16 int a[N<<2],s[N<<2];
17 
18 int main()
19 {
20     freopen("a.in","r",stdin);freopen("a.out","w",stdout);
21     scanf("%d",&n);
22     for (int i=1;i<=n;i++)
23         scanf("%d",&a[i]),a[n+i]=a[i];
24     for (int i=1;i<=n*2;i++)
25     {
26         if (i==cnt+n)
27             break;
28         s[i]=s[i-1]+a[i]-1;
29         while (s[i]<s[cnt-1])
30             cnt++;
31     }
32     LL ans=0;
33     int l=cnt+n-1,r=cnt+n-1;
34     while (r>=cnt)
35     {
36         while (!a[l]) 
37             l--;
38         ans+=(LL)(r-l)*(r-l);
39         a[l]--;
40         r--;
41     }
42     printf("%lld
",ans);
43     return 0;
44 }