POJ 3111 K Best + poj 2976 Dropping tests (二分，最大化平均值）

这两题类似，都是用二分枚举 x 然后通过式子变形判断是否大于0

注意精读问题和循环次数，过大会TLE

题目：

E - Dropping tests

Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status

Appoint description:

Description

In a certain course, you take n tests. If you get a_i out of b_i questions correct on test i, your cumulative average is defined to be

Given your test scores and a positive integer k, determine how high you can make your cumulative average if you are allowed to drop any k of your test scores.

Suppose you take 3 tests with scores of 5/5, 0/1, and 2/6. Without dropping any tests, your cumulative average is . However, if you drop the third test, your cumulative average becomes .

Input

The input test file will contain multiple test cases, each containing exactly three lines. The first line contains two integers, 1 ≤ n ≤ 1000 and 0 ≤ k < n. The second line contains n integers indicating a_i for all i. The third line contains n positive integers indicating b_i for all i. It is guaranteed that 0 ≤ a_i ≤ b_i ≤ 1, 000, 000, 000. The end-of-file is marked by a test case with n = k = 0 and should not be processed.

Output

For each test case, write a single line with the highest cumulative average possible after dropping k of the given test scores. The average should be rounded to the nearest integer.

Sample Input

Sample Output

83
100

Hint

To avoid ambiguities due to rounding errors, the judge tests have been constructed so that all answers are at least 0.001 away from a decision boundary (i.e., you can assume that the average is never 83.4997).

代码：

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <cmath>
 5 using namespace std;
 6 
 7 #define LL long long
 8 #define MAXN 1000+10
 9 int n,k;
10 double a[MAXN]  ,b[MAXN];
11 double tmp[MAXN];
12 bool cmp(double x , double y)
13 {
14     return x>y;
15 }
16 bool C(double mid)
17 {
18     int  num = n-k;
19 //    cout<<"mid" <<mid<<endl;
20     for(int i=0;i<n;i++)
21     {
22         tmp[i] = 100*a[i] - mid*b[i];
23     }
24     sort( tmp, tmp+n,cmp);
25 
26     double ret= 0;
27     for(int i=0;i<num;i++)
28     {
29         ret += tmp[i];
30       //  cout<<ret <<" " <<tmp[i]<<endl;
31     }
32 
33     if( ret >= 0) return true;
34     return false;
35 }
36 
37 
38 int main()
39 {
40     while(scanf("%d%d",&n,&k)!=EOF)
41     {
42         if( n==0 )break;
43 
44         for(int i=0;i<n;i++)
45         {
46             scanf("%lf",&a[i]);
47         }
48 
49         for(int i=0;i<n;i++)
50         {
51             scanf("%lf",&b[i]);
52         }
53 
54         double lb = 0 , ub =101;
55         double mid;
56         LL ans = 0;
57         for(int i=0;i<100;i++)
58         {
59             double mid = (lb+ub)/2;
60             if(C(mid))
61             {
62                 lb =mid;
63                 ans = round(mid);
64             }
65             else
66                 ub = mid;
67         }
68         printf("%lld
",ans);
69 
70     }
71 
72     return 0;
73 }

题目：

F - K Best

Time Limit:8000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64u

Submit Status

Appoint description:

Description

Demy has n jewels. Each of her jewels has some value v_i and weight w_i.

Since her husband John got broke after recent financial crises, Demy has decided to sell some jewels. She has decided that she would keep k best jewels for herself. She decided to keep such jewels that their specific value is as large as possible. That is, denote the specific value of some set of jewels S = {i₁, i₂, …, i_k} as

Demy would like to select such k jewels that their specific value is maximal possible. Help her to do so.

Input

The first line of the input file contains n — the number of jewels Demy got, and k — the number of jewels she would like to keep (1 ≤ k ≤ n ≤ 100 000).

The following n lines contain two integer numbers each — v_i and w_i (0 ≤ v_i ≤ 10⁶, 1 ≤ w_i ≤ 10⁶, both the sum of all v_i and the sum of all w_i do not exceed 10⁷).

Output

Output k numbers — the numbers of jewels Demy must keep. If there are several solutions, output any one.

Sample Input

Sample Output

1 2

代码：

 1 #include <algorithm>
 2 #include <cstdio>
 3 #include <iostream>
 4 #include <cmath>
 5 using namespace std;
 6 #define MAXN 100000+10
 7 #define LL long long
 8 int v[MAXN];
 9 int w[MAXN];
10 int ans[MAXN];
11 struct P
12 {
13     double t;
14     int pos;
15     bool operator < (const P& x) const
16     {
17         return t>x.t;
18     }
19 };
20 P tmp[MAXN];
21 int n,k;
22 bool C(double mid)
23 {
24     for(int i=0;i<n;i++)
25     {
26         tmp[i].t = v[i] - mid*w[i];
27         tmp[i].pos=i;
28     }
29     sort(tmp,tmp+n);
30     double ret = 0;
31     for(int i=0;i<k;i++)
32     {
33         ret += tmp[i].t;
34         ans[i] = tmp[i].pos;
35     }
36     return ret>=0;
37 }
38 
39 int main()
40 {
41     scanf("%d%d",&n,&k);
42 
43     for(int i=0;i<n;i++)
44     {
45         scanf("%d%d",&v[i],&w[i]);
46     }
47     double lb = 0 , rb = 10000000;
48 
49     for(int i=0;i<50;i++)
50     {
51         double mid = (lb+rb)/2;
52         if( C(mid) )lb = mid;
53         else
54             rb = mid;
55     }
56     for(int i=0;i<k;i++)
57     {
58         if(i != k-1)
59             printf("%d ",ans[i]+1);
60         else
61             printf("%d
",ans[i]+1);
62     }
63     return 0;
64 }

POJ 3111 K Best + poj 2976 Dropping tests (二分， 最大化平均值）

POJ 3111 K Best + poj 2976 Dropping tests (二分，最大化平均值）