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

Solution

感觉直接按照题意模拟即可。题目要求次数最少字典序最小，我们尽量使得

i \ne j

。所以直接从前往后枚举第一个数，然后判断一下减掉两个非最大值的数，是否合法（不会使操作次数增加），如果合法或当前数就是最大值，就取剩余非零且

id

最小的数，否则取最大的数。剩余非零的数字集合明显可以用并查集或 set 维护，维护最大的数及其位置则可以用线段树维护。然后就是还要特判一下当前和为奇数的情况，看能否选择

i,i

。感觉实现细节还是有点多的，不过仔细想想应该也能像清楚。

Code

CPP

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

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

文章操作

Solution

Code

相关推荐

评论

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