题目链接:https://ac.nowcoder.com/acm/problem/213315
到主站看:https://blog.csdn.net/weixin_43346722/article/details/109409248
题目
给一个长度为 的正整数序列 ,每次操作可以选择两个相邻的位置,让一个元素 另一个元素 ,输出最少几次操作,能让所有元素相等,如果不可能实现,请输出 "-1",不含引号。
输入
第一行一个整数 ,表示 组数据。
每组数据第一行一个整数 ,第二行 个数字表示 序列,
输出
对于每组数据,输出一个整数表示答案。
样例输入
3 3 1 3 2 3 2 2 3 5 1 2 3 1 3
样例输出
1 -1 3
数据范围
保证
- 的测试数据,
- 的测试数据,
- 的测试数据,
- 的测试数据,
- 的测试数据,
思路
这道题我觉得挺模拟的。
我们可以发现,操作让一个数 ,另一个数 。那这些数的总和是一直不变的。
那我们又要让它们变成全部相同的数,容易想到是变成所有数的平均数。
也可以得知,如果平均数是小数,那就没有解。
(因为每次只能 ,那无论怎么搞都是整数)
那又因为每次只会改变两个相邻的数,那我们直接从一开始枚举,然后把第 个直接变成平均数,然后造成的结果全部怼给 。
然后一直下去,记录每次把每个数变成平均数要多少步,加在一起,就是答案了。
注意!要开 long long!!!
比赛时
看了一会想到了要平均数然后每一个数到平均数。
结果忘了要开 long long,没了 分,血亏QAQ
代码
#include<cstdio> #include<algorithm> #define ll long long using namespace std; ll T, n, a[100001], sum, mid, ans, add; ll re, ***; char c; ll read() { re = 0; *** = 1; c = getchar(); while (c < '0' || c > '9') { c = getchar(); } while (c >= '0' && c <= '9') { re = re * 10 + c - '0'; c = getchar(); } return re * ***; } int main() { T = read(); for (int times = 1; times <= T; times++) { sum = ans = 0; n = read(); for (int i = 1; i <= n; i++) { a[i] = read(); sum += a[i]; } if (sum % n != 0) {//不能每个数都到平均数,就是不能每个数到同一个数 printf("-1\n"); continue; } mid = sum / n;//算出平均数 for (int i = 1; i < n; i++) { add = a[i] - mid; a[i + 1] += add;//这个数走到平均数对下一个数的改变 ans += abs(add);//每个数到平均数要多少步 } printf("%lld\n", ans); } return 0; }