【题解】C-最少移动（7612. 2020牛客NOIP赛前集训营-普及组（第五场））

C-最少移动

思路

这道题可以用前缀和做。

为序列元素， 为前缀和元素。

不难发现，当 时， ，而 不变。
同理，当 时， ，而 仍不变。

当 中所有元素相等时， 一定是一个等差数列。

举个例子：

所以可以得到结论：当 时， 中的元素不可能成等差数列，因此 中的元素不可能相等，无解。 反之则有解。

由上方发现的规律可知：在变换过程中， 总是不变的，因此可以自后向前逆推：设公差为，则 ，所以将 变成 所需的步数为 。

提示：此题必须开 long long！

代码

#include<bits/stdc++.h>

using namespace std;

int main() {
    int t;
    cin >> t;
    while(t--) {
        long long n, a[100005], f[100005], ans = 0;
        f[0] = 0;
        cin >> n;
        for(long long i = 1 ; i <= n ; i++) {
            cin >> a[i];
            f[i] = f[i-1] + a[i];
        }
        if(f[n]%n != 0) {
            cout << -1 << endl;
        }
        else {
            long long g = f[n]/n;
            for (long long i = n; i > 0; i--) {
                ans += abs(i * g - f[i]);
            }
            cout << ans << endl;
        }
    }
    return 0;
}