P3137 [USACO16FEB] Circular Barn S
题目背景
本题与 金组同名题目 在题意上一致，唯一的差别是数据范围。
题目描述
作为当代建筑的爱好者，Farmer John 建造了一个圆形新谷仓，谷仓内部
n
n
n 个房间排成环形（
3
≤
n
≤
1000
3 \\leq n \\leq 1000
3≤n≤1000），按顺时针顺序编号为
1
…
n
1\\ldots n
1…n，每个房间都有通往与其相邻的左右房间的门，还有一扇门通往外面。
现在 FJ 有
n
n
n 头奶牛，他的目标是让每个房间恰好有一头奶牛。然而不幸的是，现在奶牛们随意呆在某个房间里，第
i
i
i 个房间里有
c
i
c_i
ci 头奶牛。保证
∑
c
i
=
n
\\sum c_i =n
∑ci=n。
FJ 决定采用这样的方法来解决这个问题：让某些奶牛顺时针穿过某些房间到达指定的位置。如果一头奶牛穿过了
d
d
d 扇门，他消耗的能量为
d
2
d^2
d2。你需要帮 FJ 算出所有奶牛消耗的能量和最小值是多少。
输入格式
第一行一个整数
n
n
n，接下来
n
n
n 行，第
i
i
i 行一个整数
c
i
c_i
ci。
输出格式
输出所有奶牛最小消耗能量和。
输入输出样例 #1
输入 #1
10
1
0
0
2
0
0
1
2
2
2
输出 #1
33
C++实现
#include <cstdio>
#include <cmath>
#include <cstring>
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
const int inf=0x3f3f3f3f;
int a[1001],n,x;
int b[1001];
int c[1001],maxx=–inf,p,cnt=0;
long long ans=0;
int main(){
scanf("%d",&n);
for (int i=0;i<n;++i) {
scanf("%d",&x);
while (x) {
a[cnt++]=i;
x—;
}
}
for (int i=0;i<n;++i) b[i]=a[i]–i;
for (int i=0;i<n;++i)
if (b[i]>maxx) maxx=b[i],p=i;
c[p]=a[p];
for (int i=p–1;i>=0;—i)
c[i]=c[i+1]–1,c[i]%=n;
for (int i=p+1;i<n;++i)
c[i]=c[i–1]+1,c[i]%=n;
for (int i=0;i<n;++i) {
if (c[i]<a[i]) c[i]+=n;
ans+=((ll)c[i]–a[i])*((ll)c[i]–a[i]);
}
printf("%lld\\n",ans);
}
后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
