NOIP2012 Day1 T2(贪心+高精度)

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#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;
}

------ 本文结束 ------