思路分析
正常的思维:维护一个区间,获取该区间内的最值
其实仔细想想会发现漏洞百出,并且实现超级麻烦
最重要的是数据范围为2e5,遍历一遍再加上维护区间最值的时间至少为n^2*logn
肯定会超时
实际上还是个思维题!!
- 特殊之处:
a[n]
,a[n-1]
的值无法改变,所以得从他两切入
1.如果a[n-1]>a[n]
,则没救了,指定不可能的了
2.如果a[n]>=0
,则a[1]-a[n-2]
,可以全部用a[n-1]-a[n]
来代替(在a[n-1]<=a[n]
的条件下)
3.如果a[n]<0
,此时的(a[n-1]-a[n])>a[n-1]
,即a[n-1]-a[n]
已经不能用来代替了,只能看它自己本身了
C++ 代码
#include <iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int a[N];
int main()
{
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=1;i<=n; i++)
cin>>a[i];
if(a[n-1]>a[n]){
cout<<-1<<endl;
continue;
}
if(a[n]>=0){
cout<<n-2<<endl;
int k=a[n-1]-a[n];
for(int i=1; i<=n-2; i++)
cout<<i<<' '<<n-1<<' '<<n<<endl;
}
else{
bool flag=false;
for(int i=2;i<=n;i++)
if(a[i-1]>a[i]){
flag=true;
break;
}
if(flag) cout<<-1<<endl;
else cout<<0<<endl;
}
}
return 0;
}