CF1799B Equalize by Divide题解

SunnyYuan的博客 / 2023-05-14 / 原文

本蒟蒻学习了jiangly大佬的思想，来发一个题解。

大致题意：

给定一个 \(n\) 个元素的数组 \(a\)，每次可以选择 \(a[i]\) 和 \(a[j]\)，然后使 \(a[i] = \lceil \frac{a_i}{a_j} \rceil\)，如果最后可以使数组中的所有元素都相等，那么输出Yes，并输出每一个操作\(i, j\)；否则输出No。

本人不擅长使用Markdown，详细思路写在代码里面了。

// 思路：
// 1. 如果所有数字都相等，那么什么也不用干。
// 接下来的所有判断都假定所有数字不相等
// 2. 如果数组中有1，一定不可行，因为任何数字除以它还是它自己，用1除以任何数字却还是1，所以数组中有了1，就妄图改变数组中的任何一个数字。
// 3. 固定a[1], 不断地用别的数字a[i]和a[1]如以下方式操作，直到整个数组变为a[1]或者出现了2。
//	3. 1. 如果a[1] < a[i]，那么a[1] = a[1] / a[i] 上取整。
//	3. 2. 否则，a[i] = a[i] / a[1] 上取整。
// 4. 如果，整个数组变为a[1]，直接输出当前处理的步骤。
// 5. 否则，就将数组中不是2的元素，一个一个与2进行操作，再输出所有步骤。

// C++新语法：
// count(a, b, c) (a, b)的区间内c的个数
// find(a, b, c) 在(a, b)区间内找c并返回其指针

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
using PII = pair<int, int>;

const int N = 110;

int n;
int a[N];
PII ans[N * 35];
int cnt;

void solve() {
	cnt = 0;
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> a[i];
	
	if (count(a + 1, a + n + 1, a[1]) == n) {
		cout << 0 << '\n';
		return;
	}
	
	if (count(a + 1, a + n + 1, 1) >= 1) {
		cout << -1 << '\n';
		return;
	}
	
	while (count(a + 1, a + n + 1, a[1]) < n && count(a + 1, a + n + 1, 2) == 0) {
		int pos = 2;
		while (a[pos] == a[1]) {
			pos++;
		}
		
		if (a[pos] > a[1]) {
			if (a[pos] % a[1]) a[pos] = a[pos] / a[1] + 1;
			else a[pos] = a[pos] / a[1];
			ans[++cnt] = {pos, 1};
		}
		else {
			if (a[1] % a[pos]) a[1] = a[1] / a[pos] + 1;
			else a[1] = a[1] / a[pos];
			ans[++cnt] = {1, pos};
		}
	}
	
	if (count(a + 1, a + n + 1, a[1]) < n) {
		int pos2 = find(a + 1, a + n + 1, 2) - a;
		for (int i = 1; i <= n; i++) {
			while (a[i] != 2) {
				if (a[i] & 1) a[i] = a[i] / 2 + 1;
				else a[i] = a[i] / 2;
				ans[++cnt] = {i, pos2};
			}
		}
	}
	
	cout << cnt << '\n';
	for (int i = 1; i <= cnt; i++) cout << ans[i].first << ' ' << ans[i].second << '\n';
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int T;
	cin >> T;
	while (T--) solve();
	return 0;
}