牛客提高23 - C 题解

题目大意

有 个数连成环，可以互相和相邻的交换，问最少交换多少次使得每个位置上的数相同。

题解

首先最终状态是已知的。

这个问题有个很显然的性质是：必定有 个相邻的位置不用交换。

那么我们枚举交换的位置，就相当与把环化成了链。

那么接下来再考虑链怎么化？

设 表示前 个人最少需要交换的次数, 是最终状态每一位的答案,它就是

因为太菜了，然后被教做人了。

所以发现好像之前的是错的。

那个东西好像还要推。

考虑对于每一个新位置 i 它应该会减去

因为换了一个开头，每一位都要往后更改。

然后取中位数是最小的。

所以最后答案就是

代码

#include <bits/stdc++.h>
using namespace std;
#define ls (x << 1)
#define rs (x << 1 | 1)
#define mid ((l + r) >> 1)
#define int long long
#define Rep(x, a, b) for(int x = a; x <= b; ++ x)
#define Dep(x, a, b) for(int x = a; x >= b; -- x)
#define Next(i, x) for(int i = head[x]; i ; i = e[i].nxt)
int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
#define maxn 1000010
int sum, a[maxn], s[maxn];

signed main()
{
    int n = read();
    for(int i = 1; i <= n; ++ i)
    {
        a[i] = read();
        sum += a[i];
    }
    sum /= n;
    for(int i = 1; i <= n; ++ i)
    {
        a[i] -= sum;
        s[i] = s[i - 1] + a[i];
    }
    sort(s + 1, s + n + 1);
    sum = 0;
    for(int i = 1; i <= n; ++ i)
        sum += abs(s[n / 2 + 1] - s[i]);
    printf("%lld", sum);
    return 0;
}