假定 \(a_{1\sim n}\) 不对 \(n\) 取模，设最终状态为 \(b_{1\sim n}\)，令 \(S = \sum\limits_{i = 1} ^ n (b_i - a_i)\)，应满足以下条件：
-
\(b_i \bmod n\) 两两不同
-
\(m | S\)
-
\(\max\limits_{i = 1} ^ n (b_i - a_i)\)
先对 \(a\) 排序，那么可以发现最优情况下 \(b\) 也是有序的。
- 再一个结论：\((b_1,b_2,\cdots, b_n) = (x, x + 1, \cdots, x + n - 1)\)
考虑调整法，如果 \(b_1 + n\le b_n\)，令 \(b_1' = b_n - n,\ b_n' = b_1 + n\) 再排序，依然满足条件。
那么我们需要令 \(x\) 最小，枚举即可。
- 启示：不取模避免环的讨论，转化为其他条件。
点击查看代码
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define mkp make_pair
#define pir pair <ll, ll>
#define pb emplace_back
#define i128 __int128
void rd(ll &x) {
char ch;
while(!isdigit(ch = getchar())) ;
x = ch - '0';
while(isdigit(ch = getchar()))
x = (x << 1) + (x << 3) + ch - '0';
}
using namespace std;
const ll maxn = 5e5 + 10, inf = 1e18;
ll n, m, a[maxn], w, ret, sum;
multiset <ll> st;
int main() {
scanf("%lld%lld", &n, &m); w = n * (n - 1) / 2;
for(ll i = 1; i <= n; i++)
scanf("%lld", a + i), w -= a[i];
w = (w % n + n) % n; ll stp = -1;
for(ll i = 0; i < n; i++)
if(i * m % n == w) { stp = i; break; }
if(stp == -1) { puts("-1"); return 0; }
sort(a + 1, a + 1 + n); ll d = 0;
for(ll i = 1; i <= n; i++)
d = max(d, a[i] - i + 1);
for(ll i = 1; i <= n; i++) {
sum += i - 1 + d - a[i];
ret = max(ret, i - 1 + d - a[i]);
}
while(sum % m)
sum += n, ++ret;
ll g = m / __gcd(n, m);
while(sum < ret * m)
sum += n * g, ret += g;
printf("%lld", sum / m);
return 0;
}