添加链接描述

题意： 要求通过 ≤ n ≤n ≤n将序列作将序列变成非递减序列。 操作内容：选择 a x = a y ? a z a_x=a_y-a_z ax=ay?az，必须保证 x < y < z x<y<z x<y<z，也就是说，x只能排在他后面的两个数字

思路：

1. 如果序列本身有序，直接输出0
2. 发现如果 a [ n ? 1 ] > a [ n ] a[n-1]>a[n] a[n−1]>a[n]，根本无法执行操作，直接输出-1
3. 因为要对 a [ i ] a[i] a[i]进行修改时只能选择他后面的两个数字，我们从后向前遍历，当遍历到 i i i时，一定有 a [ i + 1 ] < a [ n ] a[i+1]<a[n] a[i+1]<a[n]，因为后面的已经被遍历过变成非递减序列了。所以遍历到 a [ i ] > a [ i + 1 ] a[i]>a[i+1] a[i]>a[i+1]的时候，让 a [ i ] = a [ i + 1 ] − a [ n ] a[i]=a[i+1]-a[n] a[i]=a[i+1]−a[n]。
4. 上面的思路有一个漏洞，导致wa了。如果 a [ n ] < 0 a[n]<0 a[n]<0，那么前面的所有数字也都小于0，当执行a[i]=a[i+1]-a[n]的操作时，会越减越大，比如 ( − 4 ) − ( − 2 ) = ( − 4 ) + 2 = − 2 (-4)-(-2)=(-4)+2=-2 (−4)−(−2)=(−4)+2=−2，所以如果 a [ n ] < 0 a[n]<0 a[n]<0也是不行的，无论如何都会越减越大，输出-1.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+100;
typedef pair<int,int> PII;
struct
{ 
        
	int x,y,z;
}ans[N];
long long a[N];
int n;
int main()
{ 
        
	int t;
	cin>>t;
	while(t--)
	{ 
        
		cin>>n;
		
		bool flag=1;
		for(int i=0;i<n;i++) 
		{ 
        
			cin>>a[i];
			if(i&&a[i]<a[i-1]) flag=0;			
		}
		
		if(flag)
		{ 
        
			cout<<0<<endl;
			continue;
		}
		
		if(a[n-1]<a[n-2]||a[n-1]<0) 
		{ 
        
			cout<<-1<<endl;
			continue;
		}
		
		int cnt=0;		
		for(int i=n-2;i>=0;i--)
		{ 
        
			if(a[i]>a[i+1])
			{ 
        
				a[i]=a[i+1]-a[n-1];
				ans[cnt++]={ 
        i+1,i+2,n};
			}
		}
		
		cout<<cnt<<endl;
		
		for(int i=0;i<cnt;i++)
		cout<<ans[i].x<<" "<<ans[i].y<<" "<<ans[i].z<<endl;
	}
    return 0;
}

补充：更加贪心的思路 因为题目没有要求输出最小解，并且我们每个数字都操作一次，最多操作次数也不会超过 n n n，所以只要是满足条件的序列，我们直接让从 a [ n − 2 ] a[n-2] a[n−2]开始的数字，每个数字变成 a [ n − 1 ] − a [ n ] a[n-1]-a[n] a[n−1]−a[n]。

#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e5+100;
typedef pair<int,int> PII;
long long a[N];
int n;
int main()
{ 
        
	int t;
	cin>>t;
	while(t--)
	{ 
        
		cin>>n;
		
		bool flag=1;
		for(int i=0;i<n;i++) 
		{ 
        
			cin>>a[i];
			if(i&&a[i]<a[i-1]) flag=0;			
		}
		
		if(flag)
		{ 
        
			cout<<0<<endl;
			continue;
		}
		
		if(a[n-1]<a[n-2]) 
		{ 
        
			cout<<-1<<endl;
			continue;
		}
		
		if(a[n-1]<0)
		{ 
        
			cout<<-1<<endl;
			continue;
		}
		cout<<n-2<<endl;
		
		for(int i=1;i<=n-2;i++)
		{ 
        
			cout<<i<<" "<<n-1<<" "<<n<<endl;
		}
	}
    return 0;
}