srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

SRM 662 div1 easy FoxesOfTheRoundTable

問題

問題概要

きつねの身長があたえられる. 円形に並べらた時, 隣あうきつねの身長差の絶対値の最大値Dとして, Dの最小値を求める.

解法

貪欲法でとけるみたい. 偶数番目を左側, 奇数番目を右側にして, 左側を昇順, 右側を降順にしてやればいいみたい. なんでこれでいいのかわからないので復習.

ミス

よくわからない. 高さが山のような形になればいいことがわかったんだけど, 左の山と右の山にどうわけるのかわからなかった. 2n試さないと無理だなーという感じ.

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vint;
typedef pair<int,int> pint;
typedef vector<pint> vpint;
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define all(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
const int MOD = 1e9 + 7;
const int INF = 1e9;

class FoxesOfTheRoundTable{
public:
    vector <int> minimalDifference(vector <int> h){
        vector<pair<int, int> > v;
        rep(i, h.size()){
            v.pb(mp(h[i], i));
        }
        sort(all(v));
        vector<int> l, r;
        rep(i, v.size()){
            if(i % 2 == 0) l.pb(v[i].se);
            else r.pb(v[i].se);
        }
        reverse(all(r));
        l.insert(l.end(), all(r));
        return l;
    }
};

int main(void){
    FoxesOfTheRoundTable ft;
    auto ret = ft.minimalDifference({1,99,50,50});
    for(auto u : ret){
        printf("%d ", u);
    }
    printf("\n");
    return 0;
}