题目描述

难度分:$1900$

本题分为简单和困难两个版本。

在困难版本中，$K=31$。

输入$T(\leq 500)$表示$T$组数据。

每组数据输入$n(1 \leq n \leq 20)$和长为$n$的数组$a(-20 \leq a[i] \leq 20)$。

你可以执行至多$K$次操作，每次操作：

• 选择下标$i$和$j$，执行$a[i]=a[i]+a[j]$。注意$i$可以等于$j$。

目标是使数组$a$非递减，即$a[i] \leq a[i+1]$。输出操作次数，以及每次操作的$i$和$j$，下标从$1$开始。

注意：你无需最小化操作次数，只要操作次数$\leq K$即可。

输入样例

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
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

算法

构造

如果$a$数组中没有负数，对它求前缀和就能得到一个单调不减的数组；如果$a$数组中没有正数，对它求后缀和就能得到一个单调不减的数组，两种情况都操作了$n-1$次。

此时在$n=20$这个极限情况下，已经操作$19$次了，最多只能再操作$12$次。设数组中的最大值为$mx$，数组中的最小值为$mn$：

1. $mx \geq |mn|$，统计一下负数的个数$neg$，如果$neg \leq 12$，就将所有负数加上$mx$变成非负数；如果$neg \gt 12$就将正数变为非正数，此时正数不超过$7$个，随便找一个负数倍增到绝对值超过$mx$，由于$a$中的元素最大就是$20$，所以最多倍增$5$次一定可以得到一个数$x$，使得所有正数加上$x$都会小于等于$0$，这时候操作次数不会超过$5+7=12$。
2. $mx \lt |mn|$，统计一下正数的个数$pos$，如果$pos \leq 12$，就将所有正数加上$mn$变成非正数；如果$pos \gt 12$就将负数变为非负数，此时负数不超过$7$个，随便找一个正数倍增到绝对值超过$|mn|$，同样最多倍增$5$次一定可以得到一个数$x$，使得所有负数加上$x$都会大于等于$0$，这时候操作次数也不会超过$5+7=12$。

复杂度分析

时间复杂度

先遍历一遍数组获得最大值$mx$和最小值$mn$，时间复杂度为$O(n)$；然后按照$|mx|$和$|mn|$的关系分类进行构造，将负数变为非负，或将正数变为非正，需要遍历数组，时间复杂度也是$O(n)$。因此，算法整体的时间复杂度为$O(n)$。

空间复杂度

除了输入的数组$a$，整个算法流程只使用了有限几个变量，因此额外空间复杂度为$O(1)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 25;
int t, n, a[N];

void solve() {
    int imn = min_element(a + 1, a + n + 1) - a;
    int imx = max_element(a + 1, a + n + 1) - a;
    int mn = a[imn], mx = a[imx];
    if(mn >= 0) {
        // 没有负数
        printf("%d\n", n - 1);
        for(int i = 2; i <= n; i++) {
            printf("%d %d\n", i, i - 1);
        }
    }else if(mx <= 0) {
        // 没有正数
        printf("%d\n", n - 1);
        for(int i = n - 1; i >= 1; i--) {
            printf("%d %d\n", i, i + 1);
        }
    }else {
        // 一般情况
        int neg = 0, pos = 0;
        for(int i = 1; i <= n; i++) {
            neg += a[i] < 0? 1: 0;
            pos += a[i] > 0? 1: 0;
        }
        if(mx >= -mn) {
            if(neg <= 12) {
                // 把负数变成非负数
                printf("%d\n", neg + n - 1);
                for(int i = 1; i <= n; i++) {
                    if(a[i] < 0) printf("%d %d\n", i, imx);
                }
                // 前缀和
                for(int i = 2; i <= n; i++) {
                    printf("%d %d\n", i, i - 1);
                }
            }else {
                // 把正数变成非正数
                int x = mn, cnt = 0;
                while(-x < mx) {
                    x *= 2;
                    cnt++;
                }
                printf("%d\n", cnt + pos + n - 1);
                for(int i = 0; i < cnt; i++) {
                    printf("%d %d\n", imn, imn);
                }
                for(int i = 1; i <= n; i++) {
                    if(a[i] > 0) printf("%d %d\n", i, imn);
                }
                // 后缀和
                for(int i = n - 1; i >= 1; i--) {
                    printf("%d %d\n", i, i + 1);
                }
            }
        }else {
            if(pos <= 12) {
                // 把所有正数变为非正
                printf("%d\n", pos + n - 1);
                for(int i = 1; i <= n; i++) {
                    if(a[i] > 0) printf("%d %d\n", i, imn);
                }
                // 后缀和
                for(int i = n - 1; i >= 1; i--) {
                    printf("%d %d\n", i, i + 1);
                }
            }else {
                // 把所有负数变为非负
                int x = mx, cnt = 0;
                while(x < -mn) {
                    x *= 2;
                    cnt++;
                }
                printf("%d\n", cnt + neg + n - 1);
                for(int i = 0; i < cnt; i++) {
                    printf("%d %d\n", imx, imx);
                }
                for(int i = 1; i <= n; i++) {
                    if(a[i] < 0) printf("%d %d\n", i, imx);;
                }
                // 前缀和
                for(int i = 2; i <= n; i++) {
                    printf("%d %d\n", i, i - 1);
                }
            }
        }
    }
}

int main() {
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        solve();
    }
    return 0;
}