1. 题目
这道题大概意思就是要对一个整形数列进行调整，用使其成为一个非递减数组。
调整的方式是，将某个位置上的数加到另一个位置上。
输入
第一行输入一个整数N，表示该整形数列有N个元素（2 <= N <= 50）；
第二行输入一个含N个元素的整形数列{}（
<=
<=
）。
输出
第一行输出一个整数m表示调整共花费了多少步（m <= 2N，只要步数不超过2N都算过关）；
接下来输出m行，每一行表示将前一个数所对应位置的元素，加到后一个数所对应位置的元素上。
例如，在第一个例子中，输出的第一行表示调整共用两部，第一步将
加到
上，第二步将
2. 最终版解法
怎么越来越短了？这次也是一遍过了，可能是做题把实力提升了？
2.1 思路
1. 既然题上将步数限制在了2N步之内，那么我们就应该尽可能的减少步数，以防步数超过限制。
2. 要减少步数，我们第一时间想到的就是每次调整都用绝对值最大的数去调整其他数字的值，这样可以尽快减小两个数之间的差距。但问题是，始终用绝对值最大的数来调整，真的是最快的吗？
3. 当我们在遍历数组的过程中遇到递减的位置时我们就要进行调整，如果我们是正向遍历数组的，那么最好调整两个数中靠后的数，因为对前一个数调整可能导致之前调整好的关系发生改变。反之则对靠前的数进行调整。
4. 那么什么时候正向遍历数组，什么时候反向遍历数组呢？正向遍历数组时，我们只能对后一个数进行调整，那么绝对值最大的数应该是一个正数；反向遍历时同理，绝对值最大的数应该是一个负数。
5. 接下来对第二点提出的问题进行解答。假设绝对值最大的数是一个正数，那么我们就正向遍历数组，又假设题目所给的样例是一个这样一个数列：
并且，，在
以后，数列保持递增。
根据所给的条件，我们只需要将加到
就可以使得数列成为一个递增数列。
但如果我们每次都用绝对值最大的数来调整的话，就会遵循以下步骤:
1. 将
加到
2. 此时
，那么我们又将
3. 以此类推，我们共需要n-2步。
虽然这样做依然没有超过2N次的限制，但不排除有类似的更加极端的情况，而且这样写未免有点太粗暴丑陋了。
而导致这种情况的原因就是，绝对值最大的那个数的绝对值实在太大了，每次用它来调整时，确实解决了当前两数为递减的问题，但是却导致之后本没有递减的地方出现了递减。
6. 所以，我们在调整时应该找到能使得当前递减变为递增的绝对值最小的数。
7. 为了找到这个数，我们应该对数列进行排序，这样我们才能依次去找。
8. 但我们肯定不能直接对原数组进行排序，因为这样我们就会丢失掉位置信息，而储存排序之后的信息的数组中的元素，最好能找到自己对应的位置信息。
9. 我们采用的方法是，定义一个int* 类型的数组，将每个原数组中每一个元素的地址依次存入，根据解引用后的大小来对地址排序。
2.2 代码
#include <stdio.h>
#include <stdlib.h>
typedef struct step//记录每一步的两个数据
{
int e1;
int e2;
}step;
int addcmp(const void* e1, const void* e2)
{
return **(int**)e1 - **(int**)e2;
}
int main()
{
int n = 0, m = 0;//m为计数器
scanf("%d", &n);
int flag = 1;
int* arr = (int*)malloc(sizeof(int) * n);
int** add = (int**)malloc(sizeof(int*) * n);
step* mstep = (step*)malloc(sizeof(step) * (2*n));
for(int i = 0; i < n; i++)
{
scanf("%d", &arr[i]);
if(i > 0&&arr[i] < arr[i-1])
flag = 0;
add[i] = &arr[i];
}
if(flag)
{
printf("%d\n", m);
return 0;
}
qsort(add, n, sizeof(int*), addcmp);
if((*add[n-1]) + (*add[0]) >= 0)//最大值的绝对值较大或全为正数
{
for(int i = 0; i < n-1; i++)//遍历arr数组并调整;
{
if(arr[i] > arr[i+1])
{
if(arr[i+1] + *add[n-1] < arr[i])//加最大的数都没效果
{
arr[i+1] += *add[n-1];
mstep[m].e1 = add[n-1] - arr;
mstep[m].e2 = i + 1;
m++;
qsort(add, n, sizeof(int*), addcmp);
}
for(int j = n - 1; j >= -1; j--)
{
if(j == -1 || arr[i+1] + *add[j] < arr[i])
{
arr[i+1] += *add[j+1];
mstep[m].e1 = add[j+1] - arr;
mstep[m].e2 = i + 1;
m++;
qsort(add, n, sizeof(int*), addcmp);
break;
}
}
}
}
}
else//最小值的绝对值较大或全为负数
{
for(int i = n - 2; i >= 0; i--)//遍历arr数组并调整;
{
if(arr[i] > arr[i+1])
{
if(arr[i] + *add[0] > arr[i+1])//加最小的负数都没用
{
arr[i] += *add[0];
mstep[m].e1 = add[0] - arr;
mstep[m].e2 = i;
m++;
qsort(add, n, sizeof(int*), addcmp);
}
for(int j = 0; j <= n; j++)
{
if(j == n || arr[i] + *add[j] > arr[i+1])
{
arr[i] += *add[j-1];
mstep[m].e1 = add[j-1] - arr;
mstep[m].e2 = i;
m++;
qsort(add, n, sizeof(int*), addcmp);
break;
}
}
}
}
}
printf("%d\n", m);
for(int i = 0; i < m; i++)
{
printf("%d %d", mstep[i].e1 + 1, mstep[i].e2 + 1);
printf("\n");
}
free(arr);free(add);free(mstep);
return 0;
}2.3 总结
最低血压的一题，主要是题目要求太松了。
