NOIP2012 Day1 T2(贪心+高精度)

以后贪心排序多考虑考虑cmp函数的写法….
本题可以把大臣排序(不要排序国王，国王始终在第一位)，然后最后一个大臣的钱就是最多的(显然)
关键是排序的cmp怎么写
我们按照$a[i] * b[i]$排序。证明：对于最后一个大臣，它所得的钱为$W=sum / a / b$，即$W=sum / (a * b)$, 那么使$(a * b)$尽可能大，那么$W$就尽可能小。

严谨证明见算法进阶指南，采用的是临项交换的方法。

(题目数字大，要高精度，但这里没打高精度了。。)

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
using namespace std;

const int MAXN = 1000 + 10;

struct data {
    int l, r;
    bool operator < (const data &b) const {
        return l * r < b.l * b.r;
    }
}h[MAXN];

int n;

void clean() {
}
void init() {
    clean();
    n++; scanf("%d%d", &h[1].l, &h[1].r);
    for (int i=2;i<=n;i++) scanf("%d%d", &h[i].l, &h[i].r);
    sort(h+2, h+1+n);
}
void solve() {
    LL ans = 1;
    for (int i=1;i<n;i++) ans *= h[i].l;
    ans /= h[n].r;
    printf("%lld\n", ans);
}
int main() {
    #ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
    #endif
    while (scanf("%d", &n)==1) init(), solve();
    return 0;
}