Problem Link

题目大意

给定 $a_1\sim a_n$，每次操作可以给 $m$ 个不同的 $a_i$ 加一（在 $\bmod n$ 意义下），求至少几次操作能让 $a$ 变成 $0\sim n-1$ 的排列。

数据范围：$n\le 2.5\times 10^5$。

思路分析

考虑在不 $\bmod n$ 意义下确定最终的 $b_i$，要满足如下条件：

• $a_i\le b_i$。
• $b_i\bmod n$ 互不相同。
• 记 $S=\sum b_i-a_i$，那么 $m\mid S$。
• $\max \{b_i-a_i\}\le \dfrac Sm$。

首先只有第一个条件和 $b$ 的相对顺序有关，为了满足这个条件，显然同时将 $a,b$ 升序排列最优。

然后考虑第四个条件，对于一组合法解 $b_1\sim b_n$，如果 $b_n-b_1\ge n$，那么调整 $b_1\gets b_n-n,b_n\gets b_1+n$。

显然不影响条件一、二、三的合法性，且此时 $b_n-a_n$ 会变小，且 $b'_1-a_1=b_n-a_1-n<b_n-a_n$，因此 $\max\{b_i-a_i\}$ 也会变小。

因此这样调整一定更优，最终一定有 $b_n-b_1<n$，即 $b_i$ 是连续的一段，存在一个 $x$ 使得 $b_i=x+i-1$。

那么逐个满足条件即可，先找到 $\max a_i-i+1$，然后调整到最近的 $x$ 使得 $\dfrac{n(2x+n-1)}2\equiv \sum a_i\pmod m$。

找到此时的 $k=\max\{b_i-a_i\}$，如果 $k> \dfrac Sm$，那么接下来就会进行若干次调整，每次会令 $x$ 加上 $d=\dfrac{m}{\gcd(n,m)}$。

此时 $k$ 加上 $\dfrac m{\gcd(n,m)}$，且 $\dfrac Sm$ 加上 $\dfrac{n}{\gcd(n,m)}$，由于 $n>m$ 因此这个调整总能结束。

时间复杂度 $\mathcal O(n\log n)$。

代码呈现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=2.5e5+5;
int n,m,a[MAXN],g;
ll sum,k=0;
signed main() {
	scanf("%d%d",&n,&m),g=__gcd(n,m);
	for(int i=0;i<n;++i) scanf("%d",&a[i]),sum+=a[i];
	if((1ll*n*(n-1)/2-sum)%g) return puts("-1"),0;
	sort(a,a+n);
	for(int i=0;i<n;++i) k=max(k,(ll)a[i]-i);
	sum=(2*k+n-1)*n/2-sum;
	while(sum%m) ++k,sum+=n;
	ll mx=0,d=m/__gcd(n,m),c=n*d/m;
	for(int i=0;i<n;++i) mx=max(mx,k+i-a[i]);
	if(mx>sum/m) {
		ll cur=(mx-sum/m-1)/(c-d)+1;
		printf("%lld\n",sum/m+cur*c);
	} else printf("%lld\n",sum/m);
	return 0;
}