这两题类似， 都是用二分枚举 x 然后通过式子变形判断是否大于0
注意精读问题和循环次数， 过大会TLE
题目：
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
.
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 ai for all i. The third line contains n positive integers indicating bi for all i. It is guaranteed that 0 ≤ ai ≤ bi ≤ 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).
代码：
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 }
题目：
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
.
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 — 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
代码：
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 }