G

题面

1635/c
Problem - 1635c - Codeforces
给你一个数组a
的n个
元素的数组。

你可以执行以下操作，但不超过n
次： 选择三个指数x,y,z
(1≤x<y<z≤n)
并将ax
替换为 ay-az
. 操作后，|ax|
需要小于1018
.

你的目标是使得到的数组不递减。如果有多种解决方案，你可以输出任何一种。如果不可能实现，你也应该报告。

输入
每个测试包含多个测试案例。第一行将包含一个单一的整数t
(1≤t≤10000)

• 测试用例的数量。然后t
  个测试用例紧随其后。

每个测试用例的第一行包含一个单一的整数n
(3≤n≤2⋅105)

• 数组的大小a
  .

每个测试用例的第二行包含n
整数a1,a2,…,an
(-109≤ai≤109)
的元素，a
.

可以保证所有测试用例的n之和
之和不超过2⋅105。
.

输出
对于每个测试案例，如果没有解决方案，则打印-1
如果没有解决方案，则打印一行。否则应在第一行打印一个整数m
(0≤m≤n)

• 你所执行的操作的数量。

然后，下面的第i
-行中的第i
行应该包含三个整数x、y、z
(1≤x<y<z≤n)

• 对第i
  -的操作。

如果有多个解决方案，你可以输出任何一个。请注意，在这个任务中，你不需要将操作的数量降到最低。

例子
输入复制
3
5
5 -4 2 -1 2
3
4 3 2
3
-3 -2 -1
输出拷贝
2
1 2 3
3 4 5
-1
0
注意
在第一个例子中，数组变成

[-6,-4,2,-1,2]
在第一次操作之后、

[-6,-4,-3,-1,2]
在第二次操作后变成[-6,-4,-3,-1,2]。

在第二个例子中，不可能在任何操作序列后使数组排序。

在第三个例子中，数组已经被排序，所以我们不需要进行任何操作。

1 2 3
3 2 -3- 2

1

切入点

(1≤x<y<z≤n)

思路：

分析切入点得到后两个元素无法被修改，所以后两个元素a[n],a[n-1]必定非递减才有解。
如果递减就直接输出-1；
再分析非递减情况下，
操作是把a[i] 变成 a[x] - a[y],x < y
数组中目前只有a[n]和a[n-1]的大小关系是通过分析可以确定的，所以
a[x] 和a[y]第一波操作肯定要用a[n] 和a[n-1]，
a[n-1] - a[n]由于a[n] 可能是负数。
运算结果要分类讨论：
a[n] >= 0时
由于a[n-1] < a[n]
会得到一个小于等于a[n-1]的负数，满足非递减，直接让前面的数全部变成这个值就行。
a[n] < 0时：
由于a[n-1] < a[n]
会得到一个大于a[n-1]的负数，不满足非递减，此时没有一种特殊的方法可以使数组变成非递减形式，所以只有当数组一开始就满足条件时才能够有解为0

第一反应比较棘手的操作是如何判断数组非递减

稍作思考发现原来遍历一遍就可以判断了，一点也不棘手

做这道题之前必须拥有的思路，
也就是

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 2e5 + 10;
int ar[N];
int main(){int T;cin >> T;while(T--){int n;scanf("%d",&n);for(int i = 1;i <= n;i++){scanf("%d",&ar[i]);}if(ar[n] < ar[n-1]) printf("-1\\n");else{if(ar[n] >= 0){int ans  = 0;for(int i = 1;i <= n-2;i++){ar[i] = ar[n-1] - ar[n];ans++;}printf("%d\\n",ans);for(int i = 1;i <= ans;i++){printf("%d %d %d\\n",i,n-1,n);}}else{bool  flag = 0;for(int i = 1;i <= n-1;i++){if(ar[i] > ar[i+1]) flag = true;}if(flag) cout << -1 << endl;else cout << 0 << endl;}}}return 0;
}

解题套路：

暂定名为：

简单方案

通过操作让数组序列呈现某种规律，非递增，非递减，
还有此类提示：请注意，您不必最小化此任务中的操作数。
一般会存在某个值，数组里的某些元素可以全部修改为这种值，使得数组有规律。