Dual (Easy Version)
题面翻译
这是本问题的简单版本，你可以进行最多 $ 50 $ 次操作。
小 C 给你了一个数列 $ a $，长度为 $ n $。
每次操作，你选择 $ i,j $，使得 $ a_i \leftarrow a_i+a_j $，需要满足 $ 1 \le i,j \le n $。
请通过操作使得数列从左往右不降。
多测，$ n \le 20 $。
感谢@船酱魔王提供的翻译。
题目描述
Popskyy [HTML_REMOVED] tiasu - Dual
⠀
The only difference between the two versions of this problem is the constraint on the maximum number of operations. You can make hacks only if all versions of the problem are solved.
You are given an array $ a_1, a_2,\dots, a_n $ of integers (positive, negative or $ 0 $ ). You can perform multiple operations on the array (possibly $ 0 $ operations).
In one operation, you choose $ i, j $ ( $ 1 \leq i, j \leq n $ , they can be equal) and set $ a_i := a_i + a_j $ (i.e., add $ a_j $ to $ a_i $ ).
Make the array non-decreasing (i.e., $ a_i \leq a_{i+1} $ for $ 1 \leq i \leq n-1 $ ) in at most $ 50 $ operations. You do not need to minimize the number of operations.
输入格式
Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 500 $ ). The description of the test cases follows.
The first line contains a single integer $ n $ ( $ 1 \le n \le 20 $ ) — the length of the array.
The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ -20 \le a_i \le 20 $ ) — the array before performing the operations.
输出格式
For each test case, output your operations in the following format.
The first line should contain an integer $ k $ ( $ 0 \le k \le 50 $ ) — the number of operations.
The next $ k $ lines represent the $ k $ operations in order. Each of these $ k $ lines should contain two integers $ i $ and $ j $ ( $ 1 \leq i, j \leq n $ ) — the corresponding operation consists in adding $ a_j $ to $ a_i $ .
After all the operations, the array $ a_1, a_2,\dots, a_n $ must be non-decreasing.
样例 #1
样例输入 #1
10
2
2 1
4
1 2 -10 3
5
2 1 1 1 1
8
0 0 0 0 0 0 0 0
5
1 2 -4 3 -10
10
11 12 13 14 15 -15 -16 -17 -18 -19
7
1 9 3 -4 -3 -2 -1
3
10 9 8
20
1 -14 2 -10 6 -5 10 -13 10 7 -14 19 -5 19 1 18 -16 -7 12 8
20
-15 -17 -13 8 14 -13 10 -4 11 -4 -16 -6 15 -4 -2 7 -9 5 -5 17
样例输出 #1
1
2 1
3
4 4
4 4
3 4
4
2 1
3 1
4 1
5 1
0
7
3 4
3 4
5 4
5 4
5 4
5 4
5 4
15
6 1
6 1
6 1
7 2
7 2
7 2
8 3
8 3
8 3
9 4
9 4
9 4
10 5
10 5
10 5
8
3 4
3 4
2 4
2 4
2 4
2 4
1 4
1 4
3
2 1
3 1
3 1
31
14 1
18 7
13 11
15 11
6 4
5 17
19 6
19 12
10 5
11 12
1 17
15 19
16 10
14 2
16 11
20 7
7 6
9 5
3 6
6 14
17 18
18 14
12 3
17 16
8 18
13 16
9 8
14 8
16 2
11 8
12 7
31
5 12
19 13
9 1
5 17
18 19
6 16
15 8
6 9
15 14
7 10
19 7
17 20
14 4
15 20
4 3
1 8
16 12
16 15
5 6
12 10
11 15
20 3
20 19
13 14
11 14
18 10
7 3
12 17
4 7
13 2
11 13
提示
In the first test case, by adding $ a_1 = 2 $ to $ a_2 $ , we get the array $ [2, 3] $ which is non-decreasing.
In the second test case, the array changes as:
- $ [1, 2, -10, 3] $
- $ [1, 2, -10, 6] $
- $ [1, 2, -10, 12] $
- $ [1, 2, 2, 12] $
In the third test case, the final array is $ [2, 3, 3, 3, 3] $ .
全部是0，就是0
(!!!!!!!重要思维)把数字全部变成正整数或者负数，看绝对值最大的那一位，是正就全部正，负反之，为什么，如果全部是正数，无论相邻两个数的大小关系，右边加上左边的必然会使得右边大于左边，全部是负数，左边加上右边必然小于右边，这两种都可以完成排序，看绝对值是保证加上绝对值最大的那位必然会使得数组全部是正的或者负的（因为是最大）
const int N = 2e5 + 10;
int a[N];
int l[N], r[N];
void solve()
{
int n;
cin >> n;
int lin = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] == 0) lin++;
}
if (lin == n)
{
cout << "0" << '\n';
return;
}
int ans = 0;
int xb = 0;
for (int i = 1; i <= n; i++)
{
if (abs(a[i]) > abs(a[xb]))
{
xb = i;
}
}
for (int i = 1; i <= n; i++)
{
if (i == xb) continue;
ans++;
l[ans] = i;
r[ans] = xb;
}
if (a[xb] > 0)
{
for (int i = 2; i <= n; i++)
{
ans++;
l[ans] = i;
r[ans] = i - 1;
}
}
else
{
for (int i = n; i >= 2; i--)
{
ans++;
l[ans] = i - 1;
r[ans] = i;
}
}
cout << ans << '\n';
for (int i = 1; i <= ans; i++) cout << l[i] << " " << r[i] << '\n';
}
