大致题意 : 一个长度为n的数组, 通过少于n次的操作, 使得数组非递减
操作为: 选定下标x,y,z(x < y < z), a[x] = a[y] - a[z]
分析 : 一开始看错题, 以为要用最少的操纵, 就想着贪心+区间维护, 结果wa, 看一眼题解, 测试样例, 再跑去看题才发现, 不必要用最少的操作(寄 !)
若是不必要用最少的操作就很简单了, 分析一下可以得出以下结论:
1. 若a[n] > a[n-1], 则操作一定失败, 毕竟操作数最少3个, 这种情况不能操作
2. 若a[n] >= 0, 那么我们对1~n-2的数字都进行操作 a[i] = a[n-1] - a[n], 一定可以得到一个非递减的数组
3. 若a[n] < 0, 我们无论怎么操作a[i] - a[j]其结果一定是将当前数变得比前数大的, 因为是 负 - 负, 这时只有当他已排好序时, 才能成功, 操作数0
AC代码如下:
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <map>
using namespace std;typedef long long ll;
const int N = 2e5+10;int n,a[N];int main()
{int T;scanf("%d", &T);while(T -- ){int n;scanf("%d", &n);for(int i = 0; i<n; i++){scanf("%d", &a[i]);}if(a[n-1] < a[n-2]){cout<<-1<<endl;continue;}if(a[n-1]>=0){cout<<n-2<<endl;for(int i = 1; i<=n-2; i++) printf("%d %d %d\n", i, n-1, n);}else{if(is_sorted(a,a+n)) cout<<0<<endl;else cout<<-1<<endl;}}
}