AtCoder Non-decreasing(数学思维)

题目链接：https://abc081.contest.atcoder.jp/tasks/arc086_b

题目大意：有n个数，最多可以执行2*n次操作，每次可以选择将ai加到aj上，最终使得该序列满足a1<=a2<=a3....<=an。求操作过程，答案不唯一。

解题思路：我们分三种情况讨论：

　　　　　①a1~an都大于等于0，那么只要从左往右使a2+=a1，a3+=a2，.....an+=an-1.总共n-1次操作就能保证a1<=a2<=a3....<=an.

　　　　　②a1~an都小于等于0，那么只要从右往左使an-1+=an，.....a2+=a3，a1+=a2.总共n-1次操作就能保证a1<=a2<=a3....<=an.

　　　　　③a1~an中有正数也有负数，取最小值MIN和最大值MAX，若abs(MAX)>=abs(MIN)，就令a1~an都加上MAX，n次操作就可以得到情况①，总计2*n-1次操作。

　　　　　若abs(MAX)<abs(MIN)，就令a1~an都加上MIN，n次操作就可以得到情况②，总计2*n-1次操作。

　　　　　总结一下，我们只要根据abs(MAX)和abs(MIN)的大小执行2*n-1次操作，就一定可以得到满足条件的序列。

代码：

#include<cstdio>
#include<cmath>
#include<cctype>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<map>
#include<stack>
#include<string>
#define INF 0x3f3f3f3f
#define LC(a) (a<<1)
#define RC(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name)  freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define CLR(arr,val) memset(arr,val,sizeof(arr))
#define FOR(i,start,end) for(int i=start;i<=end;i++)  
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=1e3+5;

int a[N];

int main(){
    int n,ma=1,mi=1;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]<a[mi]) 
            mi=i;
        if(a[i]>a[ma]) 
            ma=i;
    }
    printf("%d
",2*n-1);
    if(abs(a[ma])>=abs(a[mi])){
        for(int i=1;i<=n;i++){
            printf("%d %d
",ma,i);
        }
        for(int i=2;i<=n;i++){
            printf("%d %d
",i-1,i);
        }
    }
    else{
        for(int i=1;i<=n;i++){
            printf("%d %d
",mi,i);
        }
        for(int i=n-1;i>=1;i--){
            printf("%d %d
",i+1,i);
        }
    }
    return 0;
}