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 ai out of bi questions correct on test i, your cumulative average is defined to be

POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值).

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 POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值). However, if you drop the third test, your cumulative average becomes POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值).

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 ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ aibi ≤ 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

3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0

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).

代码:

POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值)
 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\n",ans);
69 
70     }
71 
72     return 0;
73 }
POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值)

 

 

题目:

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 vi and weight wi.

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 = {i1, i2, …, ik} as

POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值).

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 ≤ kn ≤ 100 000).

The following n lines contain two integer numbers each — vi and wi (0 ≤ vi ≤ 106, 1 ≤ wi ≤ 106, both the sum of all vi and the sum of all wi do not exceed 107).

Output

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

Sample Input

3 2
1 1
1 2
1 3

Sample Output

1 2

代码:
POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值)
 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\n",ans[i]+1);
62     }
63     return 0;
64 }
POJ 3111 K Best + poj 2976 Dropping tests (二分, 最大化平均值)

 

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

上一篇:POJ 3294 Life Forms(后缀数组)


下一篇:8章-项目质量管理-day7