题解：CF1635C Differential Sorting
ZYXzyx1006 · · 题解
题目分析
你的目标是使得最终的数组按照非降序排列。请给出你所构造的方案的操作次数，并给出每次操作中你选择的三个整数 观察题面，显然有“构造”二字，那么就是构造题，存在规律和多解。
仔细分析题意
非降序排列就说明元素与元素可以相等，那么可以将所有数字改成同一个数满足需求。保持不下降就意味着应尽量减少靠后元素的改变，防止影响已经改好的数要再次改变。那么想到保持数组末两位元素不变，将前面的元素赋值为末两位之差。 此外需要注意，若数组本身就是非降序的，输出 0。若倒数第二位大于最后一位，样例无解。若最后一位小于 0，则无解，分两类讨论。如果倒数第二位大于最后一位和最后一位大于倒数第二位。仔细思考。
#include<bits/stdc++.h>
using namespace std;
int a[214514];
int t;
int main()
{
cin>>t;
for(int i=1; i<=t; i++)
{
bool f=0;
int n;
cin>>n;
for(int i1=1;i1<=n;i1++)
{
cin>>a[i1];
if(a[i1]<a[i1+1])
f=1; //是否已经单调上升（>=）
}
if(f==0) //说明数组已经是非降序的，无需进行操作
{
cout<<0<<endl;
continue;
}
if(a[n-1]>a[n]||a[n]<0)
cout<<-1<<endl; //无解
else //可以通过(n-2)次操作达成目标
{
cout<<n-2<<endl;
for(int j=1;j<=n-2;j++)
cout<<j<<" "<<n-1<<" "<<n<<endl;
}
}
}