ARC 086 D - Non-decreasing (600)
問題概要
N個の整数からなる数列が与えられる.
x,yについて,a[y]にa[x]を足す,という操作を繰り返して,
a[0] <= a[1] <= ... <= a[N] を満たすようにしたい.
条件を満たす2N回以内の操作を出力せよ.
そのような操作が存在することは保証されている.
2 <= N <=50 , abs(a[N]) <= 106
解法
a[i]が全て正の時, a[1] += a[0], a[2] += a[1],..., a[N-1] += a[N-2]
とすれば, 新しいa'[i]はa[i]の累積和となり条件を満たす.
全て負の時は a[N-2] += a[N-1], ... a[0] += a[1]とすれば良い.
正負が混じっている時,min(a[i]) < 0 , max(a[i]) >= 0 であり,
abs(min(a[i])) > abs(max(a[i])) の時は全てのa[i]にminを,
そうでない時は全てのa[i]にmaxを足せば上に帰着できる.
メモ
最小手数のものを求めよかと思っていた.日本語力.
コード
#include "bits/stdc++.h" #define ALL(g) (g).begin(),(g).end() #define REP(i, x, n) for(int i = x; i < n; i++) #define rep(i,n) REP(i,0,n) #define EXIST(s,e) ((s).find(e)!=(s).end()) #define pb push_back using namespace std; using ll = long long; using P = pair<int,int>; const int mod=1e9+7,INF=1<<30; const double EPS=1e-12,PI=3.1415926535897932384626; const ll LINF=1LL<<60, lmod = 1e9+7; const int MAX_N = 51; int a[MAX_N]; vector<P> ans; int main(){ int N; cin >> N ; int _min = INF, _max = -INF; int argmin,argmax; rep(i,N){ scanf("%d",a+i); if(a[i]<_min){ _min = a[i]; argmin = i; } if(a[i]>_max){ _max = a[i]; argmax = i; } } if(_min<0 && _max>0){ if(abs(_min)>abs(_max)){ // 全部負にする rep(i,N){ if(a[i]<0) continue; ans.pb(P(argmin+1,i+1)); } }else{ // 全部正にする _min = 1; rep(i,N){ if(a[i]>0) continue; ans.pb(P(argmax+1,i+1)); } } } if(_min>=0){ rep(i,N-1) ans.pb(P(i+1,i+2)); }else{ for(int i=N;i>1;i--) ans.pb(P(i,i-1)); } cout << ans.size() << endl; rep(i,ans.size()) cout << ans[i].first << " " << ans[i].second << endl; return 0; }