自动搬运

查看原文

来自洛谷，原作者为

	aleph_ Quod Erat Demonstrandum.

搬运于2025-08-24 23:17:33，当前版本为作者最后更新于2025-07-05 11:53:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意：

有一个长为 $n$ 的序列 $a$，$a_i$ 表示第 $i$ 个人的等级，共 $m$ 次训练，每次令等级最小的 $k$ 个人的等级 $+1$，求最终的序列 $a$。

Subtask $1$

通过将角色按等级从低到高排序，并每次提升等级最低的 $k$ 名角色的等级，可以直接模拟升级过程。时间复杂度为 $\mathcal{O}(mn\log n)$。

Subtask $2$

将角色按等级从低到高排序。当 $k=1$ 时，训练过程如下：

• 第一个角色的等级会持续提升。
• 当第一个和第二个角色等级相同时，之后这两个角色会交替提升等级。
• 当第一、二、三个角色等级相同时，之后这三个角色会交替提升等级。

此过程持续到所有角色等级相同，之后 $n$ 个角色会轮流提升等级。

对于每个 $1 \le i \le n$，可以通过前缀和等方法计算出前 $i$ 个角色等级相同的时刻。设该时刻不超过 $m$ 且最大的 $i$ 为 $k$，则第 $(k+1)$ 到第 $n$ 个角色的等级不会提升。此时，第 $1$ 个和第 $k$ 个角色的等级差最多为 $1$，因此可以通过角色等级总和推算出每个角色的具体等级。时间复杂度为 $\mathcal{O}(n\log n)$。

Subtask $3$

由于 $m$ 不大，可以通过快速模拟每次训练来解决问题。

假设角色已按等级从低到高排序，设第 $k$ 个角色的等级为 $x$，等级低于 $x$ 的角色数量为 $l$，等级不超过 $x$ 的角色数为 $r$。每次训练后，角色等级变化如下：

• 第 $1$ 到第 $l$ 个角色等级 $+1$。
• 第 $(l+1)$ 到第 $r$ 个角色中，有 $(k-l)$ 个角色的等级 $+1$。为方便起见，我们让第 $(l+r−k+1)$ 到第 $r$ 个角色的等级提升，这样训练后等级仍保持有序。

因此，只需在有序数组中高效完成以下操作：

• 确定 $x$、$l$、$r$。
• 对区间 $[1,l]$ 和 $[(l+r−k+1),r]$ 进行+1操作。

这可以通过带懒标记的线段树快速实现。时间复杂度为 $\mathcal{O}(m\log n)$。

Subtask $4$

与 Subtask $2$ 类似，可以观察到随着训练进行，所有角色的等级会逐渐往第 $k$ 低的等级趋近。

受到 Subtask $3$ 的启发，初始状态下，设第 $k$ 低的角色等级为 $x$，将 $n$ 个角色分为三组：

• A组：等级 $<x$。

• B组：等级在 $x$ 到 $x+1$ 之间。

• C组：等级 $>x+1$。

每次训练后中，各组角色等级变化如下：

• A组：所有角色等级 $+1$。

• B组：等级最低的 $(K−|A|)$ 个角色等级 $+1$（$|A|$ 为A组大小）。

• C组：等级不变。

为什么不把等级为 $x$ 的自成一组？因为囊括进 $x+1$ 就确保了C组等级不变，并且B组角色不会再进入C组这样美好的性质。

训练过程中，A组或C组角色可能进入B组范围，此时将其移入B组。注意到以下性质：

• 第K低的角色始终在B组，因此上述分组性质保持不变。

• B组内角色等级差 $\le 1$，因此通过管理B组的大小、等级范围及各等级对应的角色数量，即可完全掌握B组信息。

• A组角色按等级从高到低、C组角色按等级从低到高依次加入B组。

考虑A组最高等级角色或C组最低等级角色加入B组的过程。用二分查找可以快速找出角色加入B组的所需的操作次数。再往操作次数少的方向扩展B组，模拟加入过程。容易发现此类扩展总共发生 $\mathcal{O}(n)$ 次，所以总时间复杂度为 $\mathcal{O}(n\log m)$。

训练结束后，根据角色所属组别即可确定其等级。总时间复杂度为 $\mathcal{O}(n\log n+n\log m)$。

如果还对具体实现有疑问，可以参考代码的注释，自认为写的还是十分详细的。

Code

#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
using namespace std;
const int N=100005;
int n,m,k,a[N];

// 函数：模拟在区间上进行m次操作后的状态
// lowcnt: 当前区间中最小值的个数
// B: 区间总长度
// k: 区间内需要操作的元素个数
// m: 操作次数
// 返回值: <区间最小值增加量, 操作后最小值个数>
pii simulate(int lowcnt,int B,int k,int m){
    int tot=(B-lowcnt)+k*m;  // 计算总增量
    return {tot/B,B-tot%B};  // 最小值增加量为总增量除以区间长度，最小值个数为区间长度减去余数（多加到的部分，其实就是最大值个数）
}

signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    cin>>m>>k;
    sort(a+1,a+n+1);
    
    // 确定初始区间边界：包含所有与a[k]相同或比a[k]大1的元素
    int l,r;
    // 向左找第一个小于a[k]的位置，即A组终点
    for(l=k-1;l>0&&a[l]==a[k];l--);
    // 向右找第一个大于a[k]+1的位置，即C组起点
    for(r=k+1;r<=n&&a[r]<=a[k]+1;r++);

    int low=a[k]; // 当前区间的最小值
    int lowcnt=count(a+1,a+n+1,low);  // 统计区间最小值个数
    int B=r-l-1;  // 当前区间总长度
    int M=m;      // 保存原始操作次数，因为接下来会对m进行修改

    // 动态扩展区间：当还有操作次数且左右可扩展时
    while(l>0||r<=n){
        if(!m) break;  // 操作次数用完则退出
        int lm=m+1,rm=m+1;
        // 计算向左扩展所需的最小操作次数（如果左边有元素）
        if(l>=1){
            int L=0,R=m;
            while(L<=R){
                int mid=(L+R)>>1;
                pii tmp=simulate(lowcnt,B,k-l,mid);  // 模拟mid次操作后的状态
                // A组最大值+已用操作+mid次操作，也就是操作后A组最大值 >= 操作后区间最小值，就可加入B组
                if(a[l]+M-m+mid>=low+tmp.first)
                    R=mid-1;  // 满足条件则尝试减少操作次数
                else
                    L=mid+1;  // 否则需要更多操作
            }
            lm=L;  // 记录向左扩展所需的最小操作次数
        }
        
        // 计算向右扩展所需的最小操作次数（如果右边有元素）
        if(r<=n){
            int L=0,R=m;
            while(L<=R){
                int mid=(L+R)>>1;
                pii tmp=simulate(lowcnt,B,k-l,mid);  // 模拟mid次操作后的状态
                // 条件：操作后区间最大值 >= C组最大值，就可加入B组
                // 因为B组等级只有x和x+1，当最小值个数——也就是值为x的个数<区间长度时，说明最大值是x+1.
                if(low+tmp.first+(tmp.second<B)>=a[r])
                    R=mid-1;  // 满足条件则尝试减少操作次数
                else
                    L=mid+1;  // 否则需要更多操作
            }
            rm=L;  // 记录向右扩展所需的最小操作次数
        }
        
        // 如果两边扩展所需操作次数都超过剩余操作次数
        if(lm>m&&rm>m){
            pii tmp=simulate(lowcnt,B,k-l,m);  // 将剩余操作全部分配给当前区间
            low+=tmp.first;     // 更新最小值
            lowcnt=tmp.second;  // 更新最小值个数
            m=0;               // 操作次数清零
            break;             // 退出循环
        }
        
        // 否则往操作次数较少的方向进行扩展
        pii tmp=simulate(lowcnt,B,k-l,min(lm,rm));  // 模拟操作
        low+=tmp.first;      // 更新最小值
        lowcnt=tmp.second;   // 更新最小值个数
        m-=min(lm,rm);       // 消耗操作次数
        
        // 右边先加入，就往向右扩展
        if(lm>=rm){
            r++;              // 扩展右边界
            if(lowcnt==B) lowcnt++;  // 如果原区间全是最小值，扩展后最小值个数+1
        }
        // 否则向左扩展
        else{
            l--;              // 扩展左边界
            lowcnt++;         // 最小值个数+1（新元素初始是最小值）
        }
        B++;  // 区间长度增加
    }
    
    // 处理剩余操作次数（如果还有）
    pii tmp=simulate(lowcnt,B,k-l,m);
    low+=tmp.first;     // 更新最小值
    lowcnt=tmp.second;  // 更新最小值个数
    
    // 计算最终序列：
    // 1. A组元素直接加上所有操作次数
    for(int i=1;i<=l;i++){
        a[i]+=M;
    }
    // 2. B组元素（区间内元素）：前lowcnt个是最小值，剩余的是最小值+1
    for(int i=l+1;i<r;i++){
        if(i-l<=lowcnt) a[i]=low;
        else a[i]=low+1;
    }
    // 3. C组保持不变（不处理）
    
    //输出最终序列
    for(int i=1;i<=n;i++){
        cout<<a[i]<<" ";
    }
}
//Together we will build a brighter future.