不参加でした。
https://community.topcoder.com/stat?c=problem_statement&pm=14188
問題
N要素の数列集合S[i]がある。
ここから、要素対をP個選んだ時、各要素対の差の最大値が最小値になるようにしたい。
その場合の要素対の差の最大値を求めよ。
解法
まずSをソートする。
後は二分探索で許容する要素対の差の最大値を探そう。
要素対の差の最大値が定まったら、Sを小さい順に見て貪欲にその最大値以下の差である2要素を対として選べばよい。
class EllysSocks { public: int getDifference(vector <int> S, int P) { int i,j; sort(S.begin(),S.end()); vector<int> D; FOR(i,S.size()-1) D.push_back(S[i+1]-S[i]); int mi=(1<<30)-1; for(i=29;i>=0;i--) { int tmp=mi-(1<<i); int num=0; FOR(j,D.size()) if(D[j]<=tmp) num++, j++; if(num>=P) mi=tmp; } return mi; } }
まとめ
やっぱりTCO Round1はDiv2位の難易度？
