UVA 1346 Songs ( Greedy, std::nth_element )

UVa Online Judge
很明顯長度越長且頻率越小放在前面一定比較好，但我只會直覺上想到應該會是以其中一個數乘上另一個數的倒數為基準做排序。證明是查了別人的文章
http://blog.csdn.net/synapse7/article/details/17160607
看到這位大神的 code我還另外學到了 stl函數庫裡的 原來有 std::nth_element，支持線性時間將一個陣列裡排序後應當是第 n小的數排到當前第 n個位置，是利用很常聽但重來沒寫過的基於快速排序思想的 median of medians algorithm.
http://www.cplusplus.com/reference/algorithm/nth_element/

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 201602;

struct Song{
    int id; double l, f;
    Song(){}
    void read(){
        scanf("%d%lf%lf", &id, &l, &f);
    }
    bool operator < (const Song &oth) const{
        return l / f < oth.l / oth.f;
    }
} song[MAXN];

int n, s;

int main(){
    while( scanf("%d", &n) == 1 ){
        for(int i = 0; i < n; ++i)
            song[ i ].read();
        scanf("%d", &s);
        nth_element( song, song + s - 1, song + n );
        printf("%d\n", song[ s - 1 ].id);
    }
    return 0;
}