题意

有 个数。 时刻开始时第 个数自增 ， 时刻结束时可以选中一个数让其自增或者自减 ，也可以什么都不做。求可能的最小时刻 ，使得 时刻结束后所有数相等。

题解

可以转化为对每一个位置 求其为结束位置时可能的最小时刻 。则 。

到位置 之前会跑若干轮，设轮数最小为 。则 。

设数列为 。分析可知只需要关注数之间的相对大小关系，那么对于每一个位置 ，实际上希望求解的是：找到一个 ，使得 全部通过自增/自减变成 的次数最小。

容易发现最优的 就是 的中位数。找到了 就可以算出这个最小的操作次数 。然后考虑至少需要几轮才能做完这些操作，由于需要 可以算出最少需要对这 个数跑 轮。

这样就做完了。维护中位数可以用 multiset 来做。

#include <bits/stdc++.h>
#define INF 2000000000
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while(c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while(c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[200005], b[200005];
ll sum1, sum2;
multiset<int> st1, st2;
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read(), b[i] = a[i];
    sort(b + 1, b + n + 1);
}
void solve(){
    int hf = ((n + 1) >> 1);
    sum1 = sum2 = 0;
    for (int i = 1; i <= hf; ++i) 
        st1.insert(b[i]), sum1 += b[i];
    for (int i = hf + 1; i <= n; ++i)
        st2.insert(b[i]), sum2 += b[i];

    ll ans = LLONG_MAX;
    for (int i = 1; i <= n; ++i){
        int mid = *st1.rbegin();
        if (a[i] <= mid){
            st1.erase(st1.find(a[i]));
            sum1 -= a[i];
        }else {
            st2.erase(st2.find(a[i]));
            sum2 -= a[i];
            st2.insert(mid);
            sum2 += mid;
            st1.erase(st1.find(mid));
            sum1 -= mid;
        }
        if (st2.empty() || a[i] + 1 < *st2.begin()){
            st1.insert(a[i] + 1);
            sum1 += a[i] + 1;
        }else {
            st2.insert(a[i] + 1);
            sum2 += a[i] + 1;
            mid = *st2.begin();
            st1.insert(mid);
            sum1 += mid;
            st2.erase(st2.find(mid));
            sum2 -= mid;
        }
        mid = *st1.rbegin();
        ll tt1 = 1ll * hf * mid - sum1 + sum2 - 1ll * (n - hf) * mid;
        ll min_turn = max(0ll, (tt1 - i - 1) / n + 1);
        ans = min(ans, min_turn * n + i); 
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}