「WyOJ Round 1」炽 · 踏浪而歌

· · 题解

Solution

算法标签： 贪心。

最小次数分为两种情况：

  1. 最大值 > 总和 - 最大值：最大值。

考虑依据答案进行贪心输出字典序最小的方案，令初始的最小次数为 \text{ans}。那么，使用 set 维护还未变成 0 的位置，每次只有 3 种变换方式：

  1. 将最小位置减 1。
  2. 最小位置和次小位置同时减 1。
  3. 最小位置和最大值位置同时减 1。

存在第一种方式是显然的，对于第 2 种是因为第 1 种只有在和是偶数的时候才能执行。第 3 种是因为第 2 种有时候因为最大值过大而不能再减。

于是，只需要维护最大值（使用线段树或 set 维护）并每次一次分讨这三种情况是否可行即可输出字典序最小的方案。

Code

// std
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
using pii = pair<int, int>;

int ilog(int x) { return 32 - __builtin_clz(x); }
template <class Info>
struct SGT {
    std::vector<Info> info;
    int N;
    SGT() {}
    SGT(int _N) { N = 1 << ilog(_N), info.resize(2 * N, Info()); }
    SGT(std::vector<Info> _info) {
        N = 1 << ilog(_info.size());
        info.resize(N * 2, Info());
        for (int i = N; i < N + _info.size(); i ++) info[i] = _info[i - N];
        for (int i = N - 1; i >= 1; i --) info[i] = info[i * 2] + info[i * 2 + 1];
    }
    void modify(int x, Info d) {
        info[x + N] = d;
        for (int i = (x + N) / 2; i >= 1; i /= 2) info[i] = info[i * 2] + info[i * 2 + 1];
    }
    Info operator[] (pair<int, int> seg) {
        int L = seg.first + N, R = seg.second + N;
        Info LS = Info(), RS = Info();
        for (; L <= R; L = L / 2, R = R / 2) {
            if (L & 1) LS = LS + info[L ++];
            if (~R & 1) RS = info[R --] + RS;
        }
        return LS + RS;
    }
    Info operator[] (int x) { return info[x + N]; }
};
const int inf = 1 << 30;
struct Info {
    int mx, pos;
    Info(int _ = -inf, int _p = 0): mx(_), pos(_p) {}
};
Info operator+ (Info a, Info b) {
    Info c;
    if (a.mx >= b.mx) c = a;
    else c = b;
    return c;
}

const int maxn = 100005;

int n;
int a[maxn];

int main() {
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n;
    SGT<Info> sgt(n + 1);
    set<int> sp;
    int sum = 0;
    for (int i = 1; i <= n; i ++) {
        cin >> a[i];
        if (!a[i]) continue;
        sgt.modify(i, {a[i], i});
        sp.insert(i), sum += a[i];
    }

    int res = sgt[{1, n}].mx * 2 > sum ? sgt[{1, n}].mx : sum + 1 >> 1;
    std::vector<pii> opt;
    while (sp.size() > 1) {
        auto check = [&](int u, int v) -> bool {
            bool ok = true;
            if (u == v) {
                a[u] --, sum --;
                sgt.modify(u, {a[u], u});
                // cout << sgt[{1, n}].mx << " " << sum << endl;
                int cur = sgt[{1, n}].mx * 2 > sum ? sgt[{1, n}].mx : sum + 1 >> 1;
                if (cur != res - 1) ok = false;
                a[u] ++, sum ++, sgt.modify(u, {a[u], u});
            } else {
                a[u] --, sum --;
                a[v] --, sum --;
                sgt.modify(u, {a[u], u});
                sgt.modify(v, {a[v], v});
                int cur = sgt[{1, n}].mx * 2 > sum ? sgt[{1, n}].mx : sum + 1 >> 1;
                if (cur != res - 1) ok = false;
                a[u] ++, a[v] ++, sum += 2;
                sgt.modify(u, {a[u], u});
                sgt.modify(v, {a[v], v});
            }
            return ok;
        };
        int u = *sp.begin(), v = *next(sp.begin()), w = sgt[{1, n}].pos;
        if (check(u, u)) {
            sum --, opt.push_back({u, u});
            a[u] --, sgt.modify(u, {a[u], u});
            if (!a[u]) sp.erase(u);
        } else if (check(u, v)) {
            opt.push_back({u, v});
            a[u] --, a[v] --, sum -= 2;
            sgt.modify(u, {a[u], u});
            sgt.modify(v, {a[v], v});
            if (!a[u]) sp.erase(u);
            if (!a[v]) sp.erase(v);
        } else {
            opt.push_back({u, w});
            a[u] --, a[w] --, sum -= 2;
            sgt.modify(u, {a[u], u});
            sgt.modify(v, {a[v], v});
            if (!a[u]) sp.erase(u);
            if (!a[w]) sp.erase(w);
        }
        res --;
    }
    if (sp.size() == 1) {
        int u = *sp.begin();
        for (int i = 1; i <= a[u]; i ++)
            opt.push_back({u, u});
    }

    cout << opt.size() << '\n';
    for (auto [u, v] : opt)
        cout << u << " " << v << '\n';

    return 0;
}