【题意】：给出n个tests，每个test有a和b两个值，现要求你从这n个test中选出k个test使得这k个test中a的和除以b的和最大。
【题解】：好明显的01分数规划。
设集合x[]，x[i]=0表示不选第i个test，x[i]=1表示选第i个test.
既我们要r = (∑a[i]*x[i]) / (∑b[i]*x[i]) 最大，且∑x[i] = k.
然后要构造子问题，详细的不想写了好麻烦。
最后上二分或者dinkelbach即可。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 using namespace std;
13 #define pb push_back
14 #define lc(x) (x << 1)
15 #define rc(x) (x << 1 | 1)
16 #define lowbit(x) (x & (-x))
17 #define ll long long
18 #define eps 1e-6
19 #define maxn 1050
20 int n, k;
21
22 struct Point {
23 int a, b;
24 double c;
25 bool operator <(const Point &x) const {
26 return c < x.c;
27 }
28 }p[maxn];
29
30 double work(double l) {
31 for(int i = 0; i < n; i++) p[i].c = 1.0 * p[i].a - l * p[i].b;
32 sort(p, p + n);
33 double sum = 0.0, suma = 0.0, sumb = 0.0;
34 for(int i = k; i < n; i++) sum += p[i].c, suma += p[i].a, sumb += p[i].b;
35 return suma / sumb;
36 }
37
38 void solve() {
39 double ans = 0.0, tmp = 0.0;
40 while(1) {
41 tmp = work(ans);
42 if(fabs(tmp - ans) < eps) break;
43 ans = tmp;
44 }
45 printf("%d\n", (int)(100.0 * (tmp + 0.005)));
46 }
47
48 int main() {
49 while(~scanf("%d%d", &n, &k)) {
50 if(!n && !k) break;
51 for(int i = 0; i < n; i++) scanf("%d", &p[i].a);
52 for(int i = 0; i < n; i++) scanf("%d", &p[i].b);
53 solve();
54 }
55 return 0;
56 }
57