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