题解：CF2103E Keep the Sum

· · 题解

山重水复疑无路，柳暗花明又一村。

脑电波题。

题意

给定一个长度为 n 的，值域为 [0,k] 的序列 a。每次操作可以选择两个和为 k 的数，任意修改它们的值，需要保证修改完之后和仍然为 k。求一种操作方案使序列单调不降，要求操作次数 \le 3\times n。

思路

首先先刷掉已经有序的、无序且无法操作的。则接下来至少有一对 a_{st}+a_{ed}=k。

发现并没有让我们求最小次数，也就是说这个最小次数可能连出题人也不会。

再结合这个并不美观的操作，我们可以想到先从宽松一点的做法开始，比如排序。

又因为操作次数要求在 O(n) 级别，我们想到：任意交换两个数对序列进行排序，所需的操作数至多只有 \pmb{n-1} 次！ 于是我们考虑如何用 3 次操作交换两个数。

这里直接给出操作方案。下图中三角下标的是被操作的数。

容易发现 a_{st},a_{ed} 的位置完全不重要，并且这么操作完 a_{st}+a_{ed} 仍然为 k，可以继续进行下一次操作。

于是我们就可以像 CF489A 那样用交换进行排序。

最后这两个 a_{st},a_{ed} 怎么办呢？我们可以在交换排序前用一次操作将 a_{st} 换到 a_1 位置（这里具体操作：将 a_{st},a_{ed} 分别设为 a_1,k-a_1），用一次操作将 a_{ed} 换到 a_n 位置（同理），最后再用一次操作将 a_{st} 设为 0，a_{ed} 设为 k 即可。

总操作次数：2+3\times(n-3)+1=3\times n-6，能够通过。

时间复杂度 O(n)。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n, T, k, a[200002], st, ed, len, rk[200002], kr[200002];
unordered_map<ll, ll> p;
struct node {
    ll x, y, z;
}op[600002];
void calc(ll x, ll y, ll z) { // change a[x] to z, a[y] to (k - z) (a[x] + a[y] = k)
    if (a[x] == z) return ;
    op[++ len] = {x, y, a[x] - z};
    a[x] = z, a[y] = k - z;
}
bool cmp(ll x, ll y) {
    return a[x] < a[y];
}
int main() {
    cin >> T;
    while (T -- ) {
        cin >> n >> k;
        p.clear();
        bool istd = 1;
        st = ed = len = 0;
        for (ll i = 1; i <= n; i ++ ) rk[i] = kr[i] = 0, cin >> a[i], istd &= (a[i] >= a[i - 1]);
        if (istd) { cout << "0\n"; continue; } // is sorted，是否已经有序
        for (ll i = 1; i <= n && ! st; i ++ ) 
            if (p[k - a[i]]) st = p[k - a[i]], ed = i;
            else p[a[i]] = i;
        if (! st) { cout << "-1\n"; continue; } // 是否有和为 k 的对
        if (st != 1) calc(st, ed, a[1]), st = 1;
        if (ed != n) calc(ed, st, a[n]), ed = n;
        //换到头尾
        for (ll i = 2; i < n; i ++ ) kr[i] = i;
        sort(kr + 2, kr + n, cmp);
        for (ll i = 2; i < n; i ++ ) rk[kr[i]] = i;
        for (ll i = 2; i < n; i ++ ) {
            ll x = i, y = kr[i], t = a[x];
            swap(kr[rk[x]], kr[rk[y]]);
            swap(rk[x], rk[y]);
            calc(1, n, a[x]);
            calc(x, n, a[y]);
            calc(y, n, t);
        }
        calc(1, n, 0);
        cout << len << "\n";
        for (ll i = 1; i <= len; i ++ ) cout << op[i].x << " " << op[i].y << " " << op[i].z << "\n";
    }
}