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

hcx2012 · 2025-06-04 19:08:49 · 题解

史上读假题最严重的一次（输入都看错了），故写篇题解庆祝反思一下。

题意

给定一个角色等级的序列 L_1\sim L_N。

共有 M 次操作，每次选择序列 L 最小的 K 个，把它们都增加 1。

这题子任务设置得相对合理，所以我们按照子任务顺序来思考本题。

Subtask 1

观察到这个 Subtask 的 N,M 特别小，所以我们可以直接按照题目中说的操作枚举即可，时间复杂度 O(M\cdot N\log{N})。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int m,k;
    cin>>m>>k;
    sort(a+1,a+n+1);
    for(int i=1;i<=m;i++){
        for(int j=1;j<=k;j++){
            a[j]++;
        }
        sort(a+1,a+n+1);
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

Subtask2

注意到，这个 Subtask 每次只需要选择一个最小的加 1。

考虑下面一个内部全是 1 的序列 L=\{1,1,\cdots\}。

• 若 L 的长度为 1，显然最终的序列为 \{1+M\}。
• 若 L 的长度为 2，则每次交替选择 L_1,L_2，宏观上看是逐渐上升的（也就是官方题解的“螺旋上升”），最终序列为：

所以再考虑任意一个序列 L，先将它从小到大排序。然后：

1. 把 L_1\sim L_x 变成相等的，花费次数不超过 M。
2. 把剩下的次数在 L_1\sim L_x 内部消化（之后选取的元素下标一定在 1\sim x 范围内）。

虽然显然可以证明操作 2 是正确的，但还是给出一下证明：

反证，如果之后选取的元素下标不在 1\sim x 范围内，那么一定有一个下标为 i 的元素 L_i，满足 L_i\le L_x，但在给定次数时只能保证 L_1=L_2=\cdots=L_x，若存在此元素，则操作 1 还可以再进行。

时间复杂度最大为排序代价，为 O(N\log{N})。

代码：

#include <bits/stdc++.h>
using namespace std;
const int N=100000+10;
int a[N];
int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    int m,k;
    cin>>m>>k;
    sort(a+1,a+n+1);
    int sum=0;
    for(int i=1;i<=n-1;i++){
        // 操作 1
        int ste=(a[i+1]-a[i])*i;
        if(sum+ste>=m){
            for(int j=1;j<=i;j++)a[j]=a[i];
            // 操作 2
            int t=m-sum;
            int round=t/i;
            t-=round*i;
            for(int j=1;j<=i;j++)a[j]+=round;
            for(int j=i;j>=1&&t>0;j--,t--)a[j]++;
            sum=m;
            break;
        }
        sum+=ste;
    }
    if(m>sum){
        // 操作 2
        for(int i=1;i<=n;i++)a[i]=a[n];
        int t=m-sum;
        int round=t/n;
        t-=round*n;
        for(int i=1;i<=n;i++)a[i]+=round;
        for(int i=n;i>=1&&t>0;i--,t--)a[i]++;
    }
    for(int i=1;i<=n;i++)cout<<a[i]<<" ";
    return 0;
}

Subtask 3

这个 Subtask 作者没有找到很好的方法。看了官方题解发现需要用线段树维护一个奇奇怪怪的东西。由于作者是蒟蒻，所以这个 Subtask 由读者自行解决。

Subtask 4

这是本题的通解。这里 M 达到了 10^9 量级，显然不能直接模拟。

考虑 M 同样很大的 Subtask 2，发现这两个 Subtask 有异曲同工之处。我们可以直接沿用 Subtask 2 的思路：（以下部分思路参考官方题解）

设 L 中第 K 大的为 x，把序列 L 分成 3 个子序列：

对于每次训练，处于各个子序列的元素执行以下操作：

宏观地看，A 和 C 中的元素有可能进入 B。具体地，A 中的元素按照从大到小顺序，C 中的元素按照从小到大顺序。