kmjp's blog

競技プログラミング参加記です

TopCoderOpen 2013 Round1B Easy EllysPairs

しばらく何も書いてなかったけど、TopCoderやらCodeForcesやらの問題は解いてた。
さて今回はTCO2013 1B。自分は本参加ではないのであとで練習参加。
結果的にMediumを1ミスしてしまったので、これ本参加してたらRound2には行けなかったな…。
http://community.topcoder.com/stat?c=problem_statement&pm=12450

問題

自然数が偶数個与えられる。
これらの自然数を2つずつペアにして和を取ったとき、ペアの和の最大値と最小値の差を最小にできる構成を選び、その差を答える。

解答

小さいものと大きいものをペアにすると全体の平均値に近い値が出ることが期待できる。
よって、全体をソートして実際にペアを作り、最大値と最小値の差を求めればよい。

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よりは簡単だね。