本蒟蒻学习了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;
}
标签:cnt,Equalize,int,题解,pos,数组,CF1799B,数字
From: https://www.cnblogs.com/PlayWithCPP/p/17399263.html