Codeforces Round #772 (Div. 2) C

题意: 给你一个序列a，每一次你可以选择三个下标 x，y，z，且,可以将$a_x=a_y-a_{z}a\_\{x\}=a\_\{y\}-a\_\{z\}$，将序列变成一个非降序列。如果可以输出操作次数，不行输出-1；

思路：

1. 如果a[n−1]>a[n]必错，因为a[n−1]无法成为一个小于等于a[n]的数。

2. 如果a[n]是正数，那么在满足性质11情况下必然可以通过n−2次构造使得前n−2个数全部变成a[n−1]−a[n]。

3. 如果a[n]是负数，前面出现的数必然都是负数才行，一旦出现a[i]>a[i+1]的情况，那么必然无法使得a[i]<=a[i+1]，因为小的负数-大的负数为大于等于0的整数，也必然a[i+1]，所以一旦有a[n]是负数，除非原数组本身是非降序，操作次数为0，否则一定是−1。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e6 + 7;
const int mod = 1e9 + 7;
const int MOD = 998244353;
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; ++i)
void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    if (is_sorted(a.begin(), a.end())) {
        cout << 0 << endl;
        return;
    }

    if (a[n - 2] > a[n - 1] || a[n - 1] < 0) {
        cout << -1 << endl;
        return;
    }

    cout << n - 2 << endl;
    for (int i = n - 3; i >= 0; i--) {
        cout << i + 1 << " " << i + 2 << " " << n << endl;
    }
}
signed main() {
    int _;
    cin >> _;
    while (_--)
        solve();
    return 0;
}