しばらく何も書いてなかったけど、TopCoderやらCodeForcesやらの問題は解いてた。
さて今回はTCO2013 1B。自分は本参加ではないのであとで練習参加。
結果的にMediumを1ミスしてしまったので、これ本参加してたらRound2には行けなかったな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12450
解答
小さいものと大きいものをペアにすると全体の平均値に近い値が出ることが期待できる。
よって、全体をソートして実際にペアを作り、最大値と最小値の差を求めればよい。
class EllysPairs { public: int getDifference(vector <int> knowledge) { int N=knowledge.size(); int mx=0,mn=50000; int i; sort(knowledge.begin(),knowledge.end()); FOR(i,N/2) { int j=knowledge[i]+knowledge[N-1-i]; mx=max(j,mx); mn=min(j,mn); } return mx-mn; } };
まとめ
さすがにDiv1よりは簡単だね。