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

· · 题解

Solution

感觉直接按照题意模拟即可。题目要求次数最少字典序最小，我们尽量使得 i \ne j。所以直接从前往后枚举第一个数，然后判断一下减掉两个非最大值的数，是否合法（不会使操作次数增加），如果合法或当前数就是最大值，就取剩余非零且 id 最小的数，否则取最大的数。剩余非零的数字集合明显可以用并查集或 set 维护，维护最大的数及其位置则可以用线段树维护。然后就是还要特判一下当前和为奇数的情况，看能否选择 i,i。感觉实现细节还是有点多的，不过仔细想想应该也能像清楚。

Code

#include<bits/stdc++.h>
#define lc (id << 1)
#define rc (id << 1 | 1)
using namespace std;
const int N = 5e5 + 10;
int a[N], n, mx[N << 2], pos[N << 2], sum;
inline void pushup(int id) {
    mx[id] = max(mx[lc], mx[rc]);
    if (mx[id] == mx[lc])pos[id] = pos[lc];
    else pos[id] = pos[rc];
}
//mx 维护最大值，pos 维护最大值的下标
inline void build(int id, int l, int r) {
}
inline void update(int id, int p, int l, int r) {
}
vector<pair<int, int> > ans;
set<int> s;
signed main() {
    ios :: sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (a[i])s.insert(i);
        //只有a[i] 非0才能放进 set，因为 set 里存的是非零的下标集
        sum += a[i];
    }
    build(1, 1, n);
    for (int i = 1; i <= n; i ++) {
        if (a[i] && s.find(i) != s.end())s.erase(i);
        if ((sum & 1) && a[i] && sum - 1 >= mx[1] * 2) {
            //sum 为奇数判断是否可以取 i,i
            ans.push_back({i, i});
            update(1, i, 1, n);
            sum --;
            a[i] --;
        }
        while (a[i]) {
            if (!s.size()) {
                //只剩下i这个数了
                ans.push_back({i, i});
                update(1, i, 1, n);
                sum --;
            } else if (a[i] == mx[1] || a[*s.begin()] == mx[1] || sum > mx[1] * 2) {
                //可以取非最大值的两个数或 a[i] 是最大值
                int x = *s.begin();
                ans.push_back({i, x});
                update(1, i, 1, n);
                update(1, x, 1, n);
                a[x] --;
                if (!a[x] && s.find(x) != s.end())s.erase(x);
                sum -= 2;
            } else {
                //只能取最大值
                int x = pos[1];
                ans.push_back({i, x});
                update(1, i, 1, n);
                update(1, x, 1, n);
                a[x] --;
                sum -= 2;
                if (!a[x] && s.find(x) != s.end())s.erase(x);
            }
            a[i] --;
        }
    }
    cout << ans.size() << '\n';
    for (auto p : ans)cout << p.first << ' ' << p.second << '\n';
    return 0;
}