G
题面
1635/c
给你一个数组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; }
解题套路：
暂定名为：
简单方案
通过操作让数组序列呈现某种规律，非递增，非递减，
还有此类提示：请注意，您不必最小化此任务中的操作数。
一般会存在某个值，数组里的某些元素可以全部修改为这种值，使得数组有规律。
