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

 int a[N];

 int main(){

     int n,ma=,mi=;

     scanf("%d",&n);

     for(int i=;i<=n;i++){

         scanf("%d",&a[i]);

         if(a[i]<a[mi])

             mi=i;

         if(a[i]>a[ma])

             ma=i;

     }

     printf("%d\n",*n-);

     if(abs(a[ma])>=abs(a[mi])){

         for(int i=;i<=n;i++){

             printf("%d %d\n",ma,i);

         }

         for(int i=;i<=n;i++){

             printf("%d %d\n",i-,i);

         }

     }

     else{

         for(int i=;i<=n;i++){

             printf("%d %d\n",mi,i);

         }

         for(int i=n-;i>=;i--){

             printf("%d %d\n",i+,i);

         }

     }

     return ;

 }

巴特西

AtCoder Non-decreasing(数学思维)

最新文章

热门文章