题解：P12701 [KOI 2022 Round 2] 升级

aleph_ · 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.