poj2976 Dropping tests(01分数规划 好题)

时间:2022-03-29 18:39:37

https://vjudge.net/problem/POJ-2976

又是一波c++AC,g++WA的题。。

先推导公式:由题意得 Σa[i]/Σb[i]<=x,二分求最大x。化简为Σ(a[i]-x*b[i])<=0,按a[i]-x*b[i]降序排列,从中取前n-m个和满足该式的话,就说明x多半是偏大了。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<cstring>
 5 #include<algorithm>
 6 #include<cmath>
 7 #include<map>
 8 #define lson l, m, rt<<1
 9 #define rson m+1, r, rt<<1|1
10 #define INF 0x3f3f3f3f
11 typedef long long ll;
12 using namespace std;
13 ll a[100010], b[100010];
14 double c[100010];
15 ll n, m;
16 bool cmp(const double a, const double b)
17 {
18     return a>b;
19 }
20 int C(double x)
21 {
22     for(int i = 0; i < n; i++){
23         c[i] = a[i]-x*b[i];
24     }
25     sort(c, c+n, cmp);//降序 
26     double ans=0;
27     for(int i = 0; i < n-m; i++){
28         ans += c[i];
29     }
30     return ans<=0;//
31 }
32 int main()
33 {
34     while(~scanf("%lld%lld", &n, &m)){
35         if(!n&&!m) break;
36         for(int i = 0; i < n; i++){
37             scanf("%lld", &a[i]);
38         }
39         for(int i = 0; i < n; i++){
40             scanf("%lld", &b[i]);
41         }
42         double lb = 0, ub = 1;
43         for(int i = 0; i < 100; i++){ 
44         //while(ub-lb>1e-6){
45             double mid = (ub+lb)/2;
46             if(C(mid)){
47                 ub = mid;
48             }
49             else lb = mid;
50             //cout << mid << endl;
51         }
52         printf("%.0lf\n", (ub*100));
53     } 
54     return 0;
55 }