Timus-1100 : Final Standings
問題概要
(id, solved)の組み合わせがN(<1.5*10^5)個与えられる。これをsolvedをキーとして降順にソートせよ。ただしバブルソートと結果が同じにならなければならない。
解法
バブルソートと同じというのは、単純に安定ソートであれば良い。なのでstable_sortを用いれば良い。ちなみに、stable_sortの実装はマージソートだったような記憶がある(少しあやふや)。最悪、stable_sortとか知らなくても元のインデックスを第2キーにするだけでよい。
acceptされたコード
計算量O(N*logN)。
#include <cstdio> #include <algorithm> using namespace std; const int MAX_N = 150000; struct team{ int id, solved; }; bool operator<(const team& lhs, const team& rhs){ return lhs.solved > rhs.solved; } team ts[MAX_N]; int main(){ int N; scanf("%d", &N); for(int i=0; i<N; i++){ scanf("%d%d", &ts[i].id, &ts[i].solved); } stable_sort(ts, ts+N); for(int i=0; i<N; i++){ printf("%d %d\n", ts[i].id, ts[i].solved); } return 0; }