A25813. 分糖果
题目描述
分糖果
题目描述
有N个小朋友从左到右排成一排，每个小朋友手中都有一定数量的糖果，且糖果总数量是N的倍数。计算出最少调整几次可以使每个小朋友的糖果数量相同。调整规则如下：
规则1:每个小朋友的糖果只能调整到左右相邻的两个小朋友手中；
规则2:第一个小朋友的糖果只能调整到第二个小朋友手中；
规则3:最后一个小朋友的糖果，只能调整到倒数第二个小朋友手中。
例如：N等于3时，1~3号小朋友原有糖果数量分别为6,4,2。
1) 1号小朋友拿出两块给2号小朋友；
2) 2号小朋友拿出两块给3号小朋友；
两次操作后三个小朋友手中糖果分别为4,4,4。即按照调整规则最少操作2次可以使3个小朋友手中糖果数量都相同。
现按照顺序给出1~N号小朋友手中原有糖果数量，按照调整规则计算出最少调整几次可以使小朋友手中的糖果数量都相同。
输入描述
第一行输入一个正整数N(N<50),表示有N个小朋友
第二行输入N个正整数(1<正整数<100),表示1到N号小朋友手中原有糖果数量，正整数之间以一个空格隔开，且所有正整数之和是N的倍数
输出描述
输出一个正整数，表示按照调整规则最少调整几次可以使小朋友手中的糖果数量都相同。
样例输入
3
642样例输出
2参考答案
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int a[n], sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
int num = 0;
for (int i = 1; i <= n - 1; i++) {
if (a[i] != sum / n) {
a[i + 1] = (a[i + 1] + a[i] - (sum / n));
a[i] = sum / n;
num++;
}
}
cout << num;
return 0;
}答案解析
// 答案2
#include <iostream>
using namespace std;
int n, s[100009]; // s用来存储每个小朋友手上的糖数
int main() {
long long sum = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> s[i];
sum += s[i];
}
int avg = sum / n; // 平均数
int cnt = 0; // 次数
for (int i = 0; i < n - 1; i++) // 左起依次判断每个小朋友手上的糖果数量
if (s[i] != avg) { // 如果该小朋友手上的糖果不为平均
s[i + 1] +=
s[i] - avg; // 由下一位小朋友给出或收取直到该小朋友糖果数为平均
cnt++; // 调整次数加一
}
cout << cnt;
return 0;
}