题解：CF1635C Differential Sorting

NEKO_Daze · 2024-10-01 15:45:19 · 题解

洛谷CF1635C || CodeForces 1635 C

简要题意

给出一个由 n 个元素组成的数组 a，你可以执行以下操作不超过 n 次：

• 选择三个元素 a_x,a_y,a_z(1 \leq x , y , z \leq n)，并将 a_x 替换为 a_y - a_z。操作完成后，|a_x| 必须小于 10^{18}。

请判断是否可以使操作后的数组不递减排列，如果有则输出任意一种方案，否则输出 -1。

思路

如果 a_{n-1} \gt a_n，那么最后两个元素永远都无法改为不递减的，答案就是 -1。

如果 a_n \geq 0，则必有一种解决方案：对每个 1\le i\le n−2 执行操作 (i,n−1,n)。

例如序列 \{4,2,1,3\} 可以进行以下操作：

• \{4,2,1,3\}\Rightarrow \{-2,2,1,3\}\Rightarrow\{-2,-2,1,3\}

否则，只有当且仅当初始数组已经为不递减排序时，才有解 0。

记录

#include <bits/stdc++.h>
using namespace std;
int t, n, a[200005];
int main ()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> t;
    while (t--)
    {
        cin >> n;
        for (int i = 0; i < n; ++i) cin >> a[i];
        if (a[n - 2] > a[n - 1]) cout << -1 << endl; //最后两项无法交换，无解
        else
        {
            if (a[n - 1] < 0)
            {
                if (is_sorted(a, a + n)) cout << 0 << endl; //除非已经排序，否则无解
                else cout << -1 << endl;
            }
            else
            {
                cout << n - 2 << endl; //一共进行n-2次操作
                for (int i = 1; i <= n - 2; ++i) cout << i << ' ' << n - 1 << ' ' << n << endl;
            }
        }
    }
    return 0;
}