ARC169D Add to Make a Permutation

Aigony · 2023-12-11 09:19:22 · 题解

更好的阅读体验 qwq

设序列 A 操作得到未被取模的最终序列 B，那么 B 应当满足如下条件：

• 令 S=\sum\limits_{i=1}^n (B_i-A_i)，有 S\bmod M=0；

考虑第三个条件，在一定的操作次数下 \max\{B_i-A_i\} 越小越容易满足条件。将 A 序列升序排序，最优的对应关系一定是将 B 也升序排序。

发现答案只和 S 的值有关，有结论：若有解，一定存在一种最优方案形如 B=(x,x+1,\cdots ,x+N)。

使用调整法证明。假设我们有一个最优的 B 序列，且 B_N-B_1>N。那么令 B_1\gets B_N-N,B_N\gets B_1+N，依次对照上文的所有条件：

• 首先因为 B_N-N>B_1，新的 B_1 比原来大。同时因为 B_1>A_1,A_N-A_1<N，有 B_1+N>A_N，满足条件 1。
• 加减 N 不改变取模后的值。
• 总和没变，S 不变。

综上，这样调整后得到的新序列仍合法。

那么我们只需考虑最小化 x 的值。

根据第一个条件可以得到 x 的下界。第四个条件 x 每增加 1，不等式左侧增加 1，右侧增加 \frac{N}{M}。因为 N>M，第四个条件也为 x 提供了下界。

接下来令 x 满足第三个条件即可，发现 x 和 x+N 是等价的，x 可以直接枚举 N 次。

时间复杂度是 \mathcal{O}(n)。

#define int long long
const int N=2.5e5+5;
int n,m,a[N],sum,x;
signed main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) x=max(x,a[i]-i+1);
    for(int i=1;i<=n;i++) sum+=(x+i-1)-a[i];
    bool flag=0;
    for(int i=0;i<=n;i++) if((sum+n*i)%m==0) {x+=i,sum+=n*i,flag=1;break;}
    if(!flag) {printf("-1\n");return 0;}
    int mx=0;
    for(int i=1;i<=n;i++) mx=max(mx,x+i-1-a[i]);
    while(mx>sum/m) mx+=m/__gcd(n,m),sum+=n*m/__gcd(n,m);
    printf("%lld\n",sum/m);
    return 0;
}