CF1635C Differential Sorting

「少女」哥伦比娅 · 2024-08-05 14:26:09 · 题解

题目传送门

题意：

给你一个长度为 n 的数组，你每次可以选择三个位置 x，y，z 并且 x \lt y \lt z。然后将 a_x 换成 a_y - a_z。你要在 n 步之内将这个数组变成非降序，问最终的数组长成什么样。

思路：

首先非降序的情况直接输出，然后对于最后两个位置，一定要是非降序的，接下来我们对于前面的 n - 2 个数，只需要等于 a_{n-1} - a_n 即可。

代码如下：

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+10;
const int INF=0x3f3f3f3f;
int t,n,a[N];
signed main(){
    cin>>t;
    while(t--){
        int f=0;
        cin>>n;
        a[0]=-1e9-1;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            f|=a[i]<a[i-1];
        }
        if(!f){
            cout<<0<<endl;
            continue;
        }
        if(a[n-1]>a[n]){
            cout<<-1<<endl;
        }else if(a[n-1]-a[n]>a[n-1]){
            cout<<-1<<endl;
        }else{
            cout<<n-2<<endl;
            for(int i=1;i<n-1;i++){
                cout<<i<<" "<<n-1<<" "<<n<<endl;
            }
        }
    }
    return 0;
}

完结撒花~