P12227 「WyOJ Round 1」炽 · 踏浪而歌题解

Ectau · 2025-11-19 12:53:56 · 题解

前言

校内模拟赛搬了这题。由于我场上不想写线段树和 set，所以最后会提供一个线性（关于 n 和值域线性）的做法。

另外一篇写得很不详细，感觉很不牛。

正文

:::info[题面]{open}

给定 1 个长度为 n 的序列 a，有如下操作：

每次选择 2 个位置 i,j，将 a_i 和 a_j 均减 1。如果 i=j，则 a_i 值只减 1 次。

问将 a 序列全部减为 0 所需的最少次数，并输出字典序最小的方案。

注：字典序最小的方案是指将所有输出的数拼接成一个序列，且使得该序列字典序尽可能小。

**注意：** $a_i$ 有可能等于 $0$。 ::: 以下我可能用到的记号：操作 $\{i,i\}$：表示选择的位置为 $i$ 和 $i$，效果为 $a_i \gets a_i - 1$。这个操作还会被叫做“单点 $-1$ 操作”。操作 $\{i,j\}$：表示选择的位置为 $i$ 和 $j$，效果为 $a_i \gets a_i - 1,a_j \gets a_j - 1$。这种操作默认 $i \ne j$。以下所有的大括号都表示操作。 ## 思路 ### 存在一个 a 大于等于 sum a 的一半的情况首先，如果其中有一个 $a_k$ 满足 $a_k \ge \lceil \frac{\sum a}{2}\rceil$，那么一定有 $(\sum a) - a_k$ 次 $a_k \gets a_k - 1,a_i \gets a_i - 1$ 的操作（$i \ne k$），即 $\{i,k\}$（暂时不考虑顺序，$\{i,k\}$ 的次数是 $a_i$）；有 $2a_k - \sum a$ 次 $a_k \gets a_k - 1$ 的操作，即 $\{k,k\}$。然后考虑给操作排序。因为题面中字典序要尽可能小，那么我们让 $\{i,k\}$ 中较小的放在前面（也就是每一次操作都形如 $\{\min(i,k),\max(i,k)\}$），操作 $\{k,k\}$ 同理。接下来给操作按字典序排序即可，时间复杂度 $O(n \log n)$。 ### 不存在一个 a 大于等于 sum a 的一半的情况接下来考虑不存在 $a_k$ 满足 $a_k \ge \lceil \frac{\sum a}{2}\rceil$ 的情况。我们可以先观察一些比较基本的性质：进行操作 $\{i,j\}$，$\sum a$ 的奇偶性不变；操作 $\{i,i\}$ 后，$\sum a$ 的奇偶性变化。最后所有的 $a=0$，$\sum a$ 的奇偶性为偶。由于我们要最小化方案数，并且目前没有 $a_i \ge \lceil \frac{\sum a}{2}\rceil$ 的元素，那么，如果 $\sum a$ 是偶数的时候，我们显然是有办法构造方案使得不使用单点 $-1$ 操作的。如果 $\sum a$ 是奇数，那么我们也有办法只用一次单点 $-1$ 操作，而且这一操作用在哪一个 $a_i \ne 0$ 的位置都可以。 :::success[证明] 下面给出这一步的证明：首先我们不加证明地认为，如果 $\sum a$ 是偶数，$\forall i \in [1,n],a_i \lt \frac{\sum a}{2}$ 的时候，我们显然是有办法构造方案使得不使用单点 $-1$ 操作的。这一块的构造方案会在下文中被提到，此处不证明。如果没有 $a_k$ 在进行一次单点 $-1$ 后，$a_k \ge \frac{\sum a}{2}$，那么转化为上面的情况，即 $\sum a$ 是偶数。如果存在 $a_k$ 使得在进行一次单点 $-1$ 后，$a_k = \frac{\sum a}{2}$，那么此时的方案为进行 $a_k$ 次形如 $\{i,k\}$ 的操作。这样的方案里没有单点 $-1$。假设存在 $a_k$ 使得在进行一次单点 $-1$ 后，$a_k \gt \frac{\sum a}{2}$，即 $a_k \ge \frac{\sum a}{2}+1$。但是，由于先前提到，没有 $a_i \ge \lceil \frac{\sum a}{2}\rceil$ 的元素，即不存在 $a_k$ 使得 $a_k \ge \frac{\sum a}{2}+1$，所以假设不成立。 ::: #### sum a 为奇数所以，我们只需要 $1$ 次单点 $-1$ 操作，然后就可以转化为 $\sum a$ 为偶数的问题。由于我们的目标是让方案的字典序最小，我们选择对第一个 $a_i>0$ 的位置进行单点 $-1$ 操作（注意是第一个 $a_i>0$ 的位置而不是 $1$ 位置）。显然这样做的字典序比任何其他可行的操作都小。接下来转化为 $\sum a$ 为偶数的情况。 #### sum a 为偶数然后考虑 $\forall k \in [1,n],a_k \lt \frac{\sum a}{2}$ 且 $\sum a$ 为偶数的问题。为了在操作次数最小的前提下让字典序最小，容易联想到每一次都执行字典序最小的可行操作，然后再判断执行之后是否还满足 $\forall k \in [1,n],a_k \lt \frac{\sum a}{2}$。显然，如果有一步的字典序不是最小的，即存在一种比当前方案的这一步骤字典序更小且可行的操作，那么选择当前步骤字典序更小的方案一定更优。在当前状态下，由于每一次操作后都还满足 $\forall k \in [1,n],a_k \leq \frac{\sum a}{2}$，所以任意选择两个不相同的位置 $i,j$，操作 $\{i,j\}$ 都是可行的操作。不妨选择当前编号最小的 $a_i>0$ 的两个位置。然后，我们只需要在执行完操作后判断是否还满足 $\forall k \in [1,n],a_k \lt \frac{\sum a}{2}$ 即可。如果满足，就继续；否则就采用 $\exist k \in [1,n],a_k = \frac{\sum a}{2}$ 的构造方案的方式。然后，我们需要一种支持以下操作的东西： + 单点 $a_i \gets a_i - 1

全局 \max
全局求和

看到这个全局 \max 我们可能会想到线段树，但是线段树是 O(n \log n) 的，并且线段树代码长（只是我懒得写），还是太不牛了。有没有什么简单一点的处理方式呢？

:::info[更简单(?)的处理方式]{open}

随便挑两个 a_i 单点 -1，维护 \sum a 肯定非常简单，难点在于维护 \max a。

由于这里的的修改操作只有 a_i \gets a_i -1，我们可以借鉴莫队维护区间众数的方式。

具体地，我们维护每一个 a_i 的出现次数 \text{freq} 和全局 \max，如果当前被 -1 的数是 \max a 且 \text{freq}(\max a) 从 1 变成 0，那么 \max a \gets \max a - 1。

否则只改变 a 和 \text{freq} 里面的值，不改变 \max a。

这一做法单次操作 O(1)，预处理关于值域线性，非常牛。

:::

但是我们还需要维护哪些地方 a_i>0，如果在一次操作后 a_i 被减成 0 了要把位置 i 删掉。我们当然可以用 set 或者 priority_queue 来维护，但是这不是优雅的线性复杂度，非常不牛。

考虑我们需要的操作：

删除
查询第一个位置
查询第二个位置

我们发现这种工作只需要链表就能完成了，所以我们使用链表。虽然我们使用单向链表就能完成，但是我不想写单向链表，所以我写了双向链表。

这里不过多解释链表怎么实现上述的操作。

总之使用链表之后，删除和查询的复杂度都变成了 O(1)，非常牛。

然后我们就有了一个初步做法：

首先判断是否 \exist k \in [1,n], a_k \ge \lceil \frac{\sum a}{2}\rceil，如果有，那么进行 (\sum a) - a_k 次 \{i,k\} 操作和 2a_k - \sum a 次 \{k,k\} 操作即可。注意操作要排序，i 与 k 之间也有顺序。

否则，如果 \sum a 是奇数，那么对当前编号最小的 a_i>0 的位置单点 -1 操作（此时 \sum a 变成偶数）。

然后，每一次进行当前字典序最小的可行操作，即选择当前编号最小的和第二小，a_i>0 的位置。如果执行操作后 \exist k \in [1,n], a_k = \frac{\sum a}{2}，那么执行 a_k 次 \{i,k\} 操作即可。

注意操作要按字典序排序。

那么我们完成了本题的 O(n \log n) 做法。

优化

那么怎么全部优化成 O(n) 呢？

我们怎么维护 \max a 的出现位置？

一边单点 -1 一边查询 \max a 的位置的行为看起来不是很优雅，但是我们发现，在整个过程中，我们只需要寻找一次 \max a 的出现位置，O(n) 遍历 a 即可。

方案里面有排序，非常不牛怎么办？

~~换成基数排序。~~

其实我们并不需要排序。上文中说的排序是对形如 \{i,k\} 的操作进行排序，因为 k 不变，那么我们只需要对 i 排序即可（显然如果 i \lt k \lt j，那么显然 \{i,k\} \lt \{k,k\} \lt \{k,j\}）。

对 i 排序只需要遍历 i \in [1,n]，然后对于 i，执行 a_i 次 \{\min(i,k),\max(i,k)\} 即可。复杂度 O(n)。

由于我们还要进行 2a_k - \sum a 次 \{k,k\} 操作，那么我们只需要将 a_k 赋值成 2a_k - \sum a 即可。

然后就一只 \log 也不需要了！

代码

附上优雅的代码：

:::info[code]

Tip：优雅的是复杂度而不是码风。

#include<cstdio>
#include<algorithm>
#include<vector>
const int N=1e5+5;
const int V=1e6+5;
using namespace std;

int a[N];
int freq[V];
int pre[N],nxt[N];

void linkdel(int p){//链表删除
    pre[nxt[p]]=pre[p];
    nxt[pre[p]]=nxt[p];
}

vector<pair<int,int> > ans;
int maxa,sum;

void decre(int i){//decrease,自减
    if(a[i]==maxa && freq[maxa]==1) maxa--;
    freq[a[i]]--;freq[a[i]-1]++;
    a[i]--;sum--;
    if(a[i]==0) linkdel(i);
}

int main(){
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",a+i);
        freq[a[i]]++;
        maxa=max(maxa,a[i]);
        sum+=a[i];
    }
    pre[n+1]=n;
    nxt[0]=1;
    for(int i=1;i<=n;i++){
        nxt[i]=i+1;
        pre[i]=i-1;
    }
    for(int i=1;i<=n;i++){
        if(a[i]==0) linkdel(i);
    }
    if(maxa*2<sum){
        if(sum%2==1){
            ans.push_back({1,1});
            decre(1);
        }
        while(maxa*2<sum){
            int u=nxt[0];
            int v=nxt[u];
            ans.push_back({u,v});
            decre(u);decre(v);
        }
    }
    if(maxa*2>=sum){
        int k=0;
        for(int i=1;i<=n;i++){
            if(a[i]==maxa){
                k=i;break;
            }
        }
        a[k]-=(sum-maxa);
        for(int i=1;i<=n;i++){
            for(int j=0;j<a[i];j++) ans.push_back({min(i,k),max(i,k)});
        }
    }
    printf("%u\n",ans.size());
    for(pair<int,int> i : ans){
        printf("%d %d\n",i.first,i.second);
    }
    return 0;
}

:::

P12227 「WyOJ Round 1」炽 · 踏浪而歌 题解

前言

正文

优化

代码

P12227 「WyOJ Round 1」炽 · 踏浪而歌题解