A33800. 移动石子
填空题
困难
知识点
题目描述
移动石子
题目描述
将N（1<N<50）堆石子围成一个圆圈，已知每堆石子的数量，且石子的总数量能被N整除。请按照如下要求移动石子，使得N堆石子的数量变为相同。
要求：可以从每堆石子中拿取石子移动到它左右相邻的两堆石子堆中。
计算出要使得N堆石子的数量变为相同，至少需要移动多少颗石子。
例如：N = 3，3堆石子顺时针方向的数量依次为2、6、7。最少需要移动3颗石子，N堆石子的数量变为相同，每堆5颗。
第1次从第一堆石子中拿1颗移动到第一堆的石子中，此时3堆石子的数量依次为3、5、7；
第2次从第三堆石子中拿2颗移动到第一堆的石子中，此时3堆石子的数量依次为5、5、5。
输入描述
第一行输入一个正整数N（1＜N＜50），表示石子的堆数
第二行输入N个正整数（1＜正整数＜100），表示顺时针方向每堆石子的原始数量，正整数之间以一个空格隔开
输出描述
输出一个整数，表示要使N堆石子的数量变为相同，最少移动的石子数量，如果原始N堆石子数量相同，则输出0
样例输入
3
2 6 7样例输出
3参考答案
#include<iostream>
#include<cmath>
using namespace std;
int a[120], b[51];
int main() {
int n, sum1 = 0, avg = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
sum1 += a[i];
a[i + n] = a[i];
}
avg = sum1 / n;
int maxc = 50000;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
b[j] = a[i + j];
}
int cnt = 0;
for (int j = 0; j < n - 1 ; j++) {
cnt += abs(b[j] - avg);
b[j + 1] += b[j] - avg;
b[j] = avg;
}
maxc = min(maxc, cnt);
}
cout << maxc;
return 0;
}
上一题
下一题