一道有趣结论题。
但是感觉官方题解说的真的有点糊。
题目链接
题意
给定一个长度为 的数组 与一个数字 ，你可以进行若干次操作：
选中 个数字，并将他们 ，若有数字到达 ，则将这个数字变为 。
求将 变为一个
的排列的最小次数，或输出无解。
题解
我们假设 在值为 时不会变成 ，并令最后的结果为 ，那么我们的最终目标是让 互不相等。
设 ，考虑 合法的条件：
- ；
- ；
- 。
考虑在步数最小的情况下，我们求出一个 最小的 。
可以证明，这个 一定是
的一个排列，可以使用反证法来证明：
设当前 合法，满足步数最小且
最小，且存在 。
令 ，。
由于 ，所以
会变小。
以前三个条件仍然满足：
，所以
不变，所以仍然有 ；
所以仍然有 ，；
所以仍然有 ，。
综上所述，步数最小且
最小的 一定为 的排列的形式。
也就是说，我们只需要考虑 为
的排列的形式。
首先我们将
从小到大排序，不难发现，此时的
递增是一定是最优的。
所以我们只需要找出一个最小的 ，使得 的 满足上面的条件。
不难发现，条件 给出的是
的下界，设 。
对于条件 ，有 。
对于条件 ，有 。
条件 则给出了关于 的额外限制，设 。
。
首先，若 ，则无解；否则，可以暴力枚举，算出
的值（不存在则无解）。
结合三个条件，便可以算出最小的 ，便能算出最小的操作次数。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include<bits/stdc++.h>
#define inf 0x3f3f3f3f3f3f3f3fll
#define debug(x) cerr<<#x<<"="<<x<<endl
using namespace std;
using ll=long long;
using ld=long double;
using pli=pair<ll,int>;
using pi=pair<int,int>;
template<typename A>
using vc=vector<A>;
inline int read()
{
int s=0,w=1;char ch;
while((ch=getchar())>'9'||ch<'0') if(ch=='-') w=-1;
while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
return s*w;
}
int a[250001];
ll s,ans;
int n,m;
int main()
{
n=read(),m=read(),ans=-inf;
for(int i=1;i<=n;i++) s+=(a[i]=read());
sort(a+1,a+n+1);
for(int i=n;i;i--) ans=max(ans-1,(ll)a[i]);
for(int i=1;i<=n;i++)
{
ll A=(ll)n*(n-1)/2-s,B=(i-1)-a[i];
ans=max(ans,(m*B-A+n-m-1)/(n-m));
}
ll C=(s-(ll)n*(n-1)/2%m+m)%m;int val=-1,g=__gcd(n,m);
for(int i=0;i<m/g;i++) if((ll)n/g*i%(m/g)*g==C){ val=i;break;}
if(val==-1){ printf("-1\n");return 0;}
ans=(ans-val+(m/g)-1)/(m/g)*(m/g)+val;
printf("%lld\n",((ll)n*(n-1)/2+ans*n-s)/m);
return 0;
}
|
感谢观看！