数组非递减排序：最多 50 次操作 - 算法题解

{"title":"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.\n\nYou are given an array a1,a2,…,an\n of integers (positive, negative or 0\n). You can perform multiple operations on the array (possibly 0\n operations).\n\nIn one operation, you choose i,j\n (1≤i,j≤n\n, they can be equal) and set ai:=ai+aj\n (i.e., add aj\n to ai\n).\n\nMake the array non-decreasing (i.e., ai≤ai+1\n for 1≤i≤n−1\n) in at most 50\n operations. You do not need to minimize the number of operations.\n\nInput\nEach test contains multiple test cases. The first line contains the number of test cases t\n (1≤t≤500\n). The description of the test cases follows.\n\nThe first line contains a single integer n\n (1≤n≤20\n) — the length of the array.\n\nThe second line contains n\n integers a1,a2,…,an\n (−20≤ai≤20\n) — the array before performing the operations.\n\nOutput\nFor each test case, output your operations in the following format.\n\nThe first line should contain an integer k\n (0≤k≤50\n) — the number of operations.\n\nThe next k\n lines represent the k\n operations in order. Each of these k\n lines should contain two integers i\n and j\n (1≤i,j≤n\n) — the corresponding operation consists in adding aj\n to ai\n.\n\nAfter all the operations, the array a1,a2,…,an\n must be non-decreasing.\n翻译成中文内容：该问题的两个版本唯一的区别在于对最大操作次数的限制。只有当所有版本的问题都解决了，才能进行黑客攻击。\n\n给定一个整数数组 a1,a2,…,an（可以为正数、负数或0）。您可以对数组执行多个操作（可能为0个操作）。\n\n在一次操作中，您选择 i,j（1≤i,j≤n，它们可以相等）并设置 ai:=ai+aj（即将 aj 添加到 ai）。\n\n在最多50次操作中使数组变为非递减（即对于1≤i≤n−1，ai≤ai+1）。您不需要最小化操作次数。\n\n输入\n每个测试包含多个测试用例。第一行包含测试用例的数量 t（1≤t≤500）。接下来是测试用例的描述。\n\n第一行包含一个整数 n（1≤n≤20）—数组的长度。\n\n第二行包含 n 个整数 a1,a2,…,an（−20≤ai≤20）—操作之前的数组。\n\n输出\n对于每个测试用例，以以下格式输出您的操作。\n\n第一行应包含一个整数 k（0≤k≤50）—操作次数。\n\n接下来的 k 行按顺序表示 k 次操作。这 k 行中的每一行应包含两个整数 i 和 j（1≤i,j≤n）—相应的操作是将 aj 添加到 ai。\n\n在所有操作之后，数组 a1,a2,…,an 必须是非递减的。