C. Differential Sorting

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

题目描述

你有一个大小为 $n$ 数组，可以选择 3 个索引 $x,y,z$ （$1\le x<y<z\le n$），并将 $a_x$ 替换为 $a_y-a_z$ ，并且 $|a_x|\le 10^{18}$。你最多可以操作 $n$ 次，操作完后使数组不递减。

输入描述

每个测试包含多个测试用例。 第一行将包含一个整数 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)——你执行的操作数。

那么接下来的 m 行中的第 i 行应该包含三个整数 x,y,z (1≤x<y<z≤n)——第 i 次操作的描述。

如果有多个解决方案，您可以输出任何一个。 请注意，您不必最小化此任务中的操作数。

样例

#1

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] 在第二次操作之后。
在第二个示例中，不可能使数组在任何操作序列之后排序。
在第三个示例中，数组已经排序，所以我们不需要执行任何操作。

解析

由 $x,y,z$ （$1\le x<y<z\le n$）这个条件可知：

1. 一定存在 $a_n\ge a_{n-1}$ ，若不存在则此序列无解，因为无法找出满足条件的 3 个索引，因此无法处理这种关系。
2. 在满足上面的条件的前提下，若 $a_n\ge 0$ 则前面的所有数字都可以使用 $a_x=a_n-a_{n-1}$ 来修正（修正为同一个数值，题目没说严格递增，因此可行）。
3. 若 $a_n<0$ 且此序列非升序，则此序列无解。
4. 若 $a_n<0$ 且此序列升序，则此序列有解。

证明：若 $a_n<0$ 且此序列非升序，则此序列无解。（我本人也只是个学渣，也不知道算不算证明，仅供参考哈）

假设该序列为 $a_i\ge a_{i+1}\le \cdots \le a_{n-1}\le a_n$ ，存在 $a_i\ge a_{i+1}$ ，从右向左看，你需要修改 $a_i$ 或 $a_{i+1}$ 其中一个，使其满足 $a_i\le a_{i+1}$ ，因为 $a_n<0$ ，为了保证整个序列不降（即保证升序），所以整个序列都是负数。根据负数减负数的性质可知，当 $-a-(-b)$ ，$-b$ 的值越小，则结果越大，反之越小。假设修改 $a_{i+1}$ ，后面的值是越来越大，$a_x=a_y-a_z$ 最终的值必然越来越小。

AC Code

public class Main {static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static PrintWriter out = new PrintWriter(new BufferedOutputStream(System.out));public static void main(String[] args) throws Exception {int T = nextInt();while(T-- != 0) {int n = nextInt();int[] A = new int[n+1];for(int i = 1; i <= n; i++) A[i] = nextInt();if(A[n] < A[n-1]) {out.println(-1);continue;}if(A[n] < 0) {boolean flag = false;for(int i = 1; i < n; i++) {if(A[i] > A[i+1]) {flag = true;break;}}if(flag) out.println(-1);else out.println(0);continue;}out.println(n-2);for(int i = 1; i < n - 1; i++) {out.printf("%d %d %d\n", i, n-1, n);}}out.flush();}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}public static String nextStr() throws Exception {st.nextToken();return st.sval;}
}