Codeforces Round #772 (Div. 2) C. Differential Sorting（思维+构造）

题目链接

https://codeforces.com/contest/1635/problem/C

题面

题意

给你一个长度为n的数组 a [ i ] a[i] a[i] ，我们有一种操作让 a [ x ] = a [ y ] − a [ z ] a[x] = a[y] - a[z] a[x]=a[y]−a[z] ，我们可以使用无限次操作让数组 a a a 变成一个非递减的数组，如果可以的话，输出操作的过程（即每一步的x、y、z），否则输出 -1

思路

因为题目中并未要求使得操作次数最小，那么我们就来思考什么情况下是不能构建的呢，于是我们分成如下几种情况讨论：

• 当序列本身就是一个非递减的，那么操作数为0
• 当 a [ n ] < a [ n − 1 ] a[n] < a[n-1] a[n] = 0 a[n] >= 0 a[n]>=0 那么，我们对前 n − 2 n-2 n−2 个数做一个 i , n − 1 , n i ,n-1,n i,n−1,n 的一个操作，那么前n-2个数就都等于 a [ n − 1 ] − a [ n ] a[n-1]-a[n] a[n−1]−a[n] 且这个数一定是比 a [ n − 1 ] a[n-1] a[n−1] 小的，因为减去的是正数，又由于 a [ n ] > = a [ n − 1 ] a[n] >= a[n-1] a[n]>=a[n−1] ，那么我们这个构建的一定是一个非递减的序列
• 如果 a [ n ] < 0 a[n] < 0 a[n]>n; bool fg = true; a[0] = -0x3f3f3f3f; for(int i = 1;i >a[i]; if(a[i]