题目链接: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;
}