第一次看的时候确实被题面吓了一跳，没有好好思考就放弃了。其实题目还是蛮简单的。
题意
对于两种操作，我们可以进行分类讨论。
当 \(a_i > a_j\) 时
操作一：将 \(a_i\) 变为了 \(2 \times a_i - a_j\)；
操作二：将 \(a_i\) 变为了 \(a_j\)。
当 \(a_i \le a_j\) 时
操作一：将 \(a_i\) 变为了 \(a_j\)；
操作二：将 \(a_i\) 变为了 \(2 \times a_i - a_j\)。
思路
观察上面的结果，我们可以发现不论 \(a_i\) 和 \(a_j\) 的大小关系如何，我们都可以通过两种操作 直接 将 \(a_i\) 变为 \(a_j\)。
那么，为了将所有数字变为相同的，我们应该选择将所有数字转换为原数组中数量最多的数，所以这道题的做法其实就是找出这个数组的众数，再用 \(n\) 将其减去，即为答案。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 200005;
int n, cnt = 1, maxn = 0;
int mode, a[N], a2[N];
int main() {
// freopen("equalize.in", "r", stdin);
// freopen("equalize.out", "w", stdout);
scanf("%d", &n);
if (n == 1) {
printf("0\n");
return 0;
}
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a2[i] = a[i];
}
sort(a + 1, a + n + 1);
// for (int i = 1; i <= n; i++) {
// cout << a[i] << endl;
// }
for (int i = 1; i < n; i++) {
if (a[i] == a[i + 1]) cnt++;
else cnt = 1;
if (cnt > maxn) {
mode = a[i];
maxn = cnt;
}
}
printf("%d\n", n - maxn);
// cout << mode << endl;
if ((n - maxn) == 0) return 0;
for (int i = 2; i <= n; i++) {
if (a2[i - 1] == mode) {
if (a2[i] > a2[i - 1]) printf("2 %d %d\n", i, i - 1);
else if (a2[i] < a2[i - 1]) printf("1 %d %d\n", i, i - 1);
a2[i] = a2[i - 1];
}
}
for (int i = n - 1; i >= 1; i--) {
if (a2[i + 1] == mode) {
if (a2[i] > a2[i + 1]) printf("2 %d %d\n", i, i + 1);
if (a2[i] < a2[i + 1]) printf("1 %d %d\n", i, i + 1);
a2[i] = a2[i + 1];
}
}
return 0;
}
//a[i] > a[j]
// 1: 2*a[i]-a[j]
// 2: a[j]
//a[i] < a[j]
// 1: a[j]
// 2: 2*a[i]-a[j]
注意：在求众数时循环条件为
i < n，所以需要特判n == 1的情况