题解：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)

。

代码

CPP

#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";
	}
}

题解：CF2103E Keep the Sum

文章操作

题意

思路

代码

相关推荐

评论

题解：CF2103E Keep the Sum