[atcoder] agc86 D - Non-decreasing

D - Non-decreasing
タイトルリンク:Non-decreasing
テーマ:
長さn(1≦n≦50)のシーケンスを与えた.毎回2つの数ax,ayを選択し,ayにaxを加算することができる.最終的にaシーケンスが低下しないようにし,問題は0 2 n回の解を保証する.操作個数および操作スキームを出力します.
データ範囲:
1≤n≤50 −106≤ai≤106
問題解決の考え方:
この問題は試合中に思いつかなかった.C問題は5分で書き終わったら電話を切った.の試合が終わった後、別のコードを見て一瞬理解した.実はこの問題aiが正数か負の数であれば、左から右へまたは右から左へ1回加算、すなわちn-1回操作すれば条件に合致すると考えられる.しかし、現在は正負があり、絶対値の最大数を記録するだけで、このn個の数にこの絶対値の最大数を加えると、彼らは記号が統一され、この操作はn回なので、2 n回で必ず解があることを保証することができる.
ACコード:

/********************************************
 *Author*        :ZZZZone
 *Created Time*  :   12/11 20:46:20 2017
 * Ended  Time*  :   12/11 21:04:29 2017
*********************************************/
#include
#include
#include
#include
#include
#include
using namespace std;

int n;
int a[55];

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