题解：CF1635C Differential Sorting

Tulip_ · 2024-07-01 17:02:57 · 题解

题意

给定一个长度为 n 的数组 a。你可以执行不超过 n 次操作，每次操作中，你可以选择三个整数 x,y,z，需要保证 1\leqslant x<y<z\leqslant n 且操作之后 \left|a_x\right|<10^{18}，然后将 a_x 替换为 a_y-a_z。

你的目标是使得最终的数组按照非降序排列。请给出你所构造的方案的操作次数，并给出每次操作中你选择的三个整数 x,y,z；或者判断根本不可能通过执行不超过 n 次操作达到目标，此时输出 -1。

思路

我们需要三个分类讨论：

1. 一开始就判断数组按照非降序排列，如果满足就输出 0。

这个就是边输入边判断，一发现不满足就标记。

2. 思考 1：哪些不满足需输出 -1

我们思考后会发现 a_n 与 a_{n-1} 的关系跟输出 -1。

a_{n-1} 大于 a_{n} 或者是 a_{n-1}-a_{n} 大于 a_{n-1}，则无法通过操作将数组变为非降序，直接输出 −1。

3. 思考 2：哪种方案可以最简单的打出来，有那种固定的更改方案吗。

这个可能有点难，那看这个。

通过思考，我发现只要满足，且有更改方案的个数都为 n-2。

对于每一次的更改，我们可以将 a_{i} 替换为 a_{n} 与 a_{n-1} 相减，这样我们就不用一个一个判断，只需要直接输出 a_i,a_n-1,a_n。

注意

• 边输入边判断时，我们要记得加上 i>1，这是因为输入第一个时，可能会将标记数标记，使得输出了 -1。

• 数组记得不要卡的刚刚好，建议设为 2 \times 10^5 +5 不然会 RE 的！

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Max=2e5+5;
int t,n,a[Max]; 
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;  
        int o=0;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            if(i>1&&a[i]<a[i-1])  o=1; 
        }
        if(o==0){
            cout<<0<<endl;
            continue;
        }else if(a[n-1]>a[n]||a[n-1]-a[n]>a[n-1]){
            cout<<-1<<endl;
            continue;
        }else{
            cout<<n-2<<endl;
            for(int i=1;i<=n-2;i++){
                cout<<i<<" "<<n-1<<" "<<n<<endl;
            }
        }
    }
    return 0;
}

讲到这应该明白了吧，快去去试一试！