POJ 2976（01分数划分+二分）

Dropping tests

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 12221		Accepted: 4273

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

POJ 2976（01分数划分+二分） .

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 2976（01分数划分+二分） . 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).

Source

Stanford Local 2005

题意：给你n对 a[i] b[i] 去掉k对使得 sigms(a)/sigma(b) 最大

后来才知道这是一道板子题

(∑ai*xi)/(∑bi*xi)求极值问题

我们可以化简 (∑ai*xi)-L*(∑bi*xi)=0；

F（L)=(∑ai*xi)-L*(∑bi*xi) 由此可以得到这个一个单调递减的函数随着L的增大而减小、

假设我们要求的最大值L为 l;

只有当F(L)无限接近0时 L=l;

对于我们如何来确定这个解

比如我们选k对我们只有判断这前K大的(ai-L*b[i])和是不是<0;因为这是单调递减的，F(L)<0--> L>l F(L)>0--> L

而我们这个题是删除k对所以只有n-k就可以了

 #include<iostream>

 #include<cstdio>

 #include<cstdlib>

 #include<cctype>

 #include<cmath>

 #include<cstring>

 #include<map>

 #include<stack>

 #include<set>

 #include<vector>

 #include<algorithm>

 #include<string.h>

 typedef long long ll;

 typedef unsigned long long LL;

 using namespace std;

 const int INF=0x3f3f3f3f;

 const double eps=0.0000000001;

 const int N=+;

 int n,k;

 int a[N],b[N];

 double ans[N];

 int judge(double x){

     double sum=;

     for(int i=;i<n;i++){

         ans[i]=a[i]-x*b[i];

     }

     sort(ans,ans+n);

     for(int i=n-;i>=n-k;i--)sum=sum+ans[i];

     if(sum>)return ;

     else

         return ;

 }

 int main(){

     while(scanf("%d%d",&n,&k)!=EOF){

         if(n==&&k==)break;

         double maxx=0.0;

         for(int i=;i<n;i++)scanf("%d",&a[i]);

         for(int i=;i<n;i++)scanf("%d",&b[i]);

         k=n-k;

         double low=;

         double high=1.0;

         double mid;

         while(low+eps<high){

             mid=(low+high)/;

             if(judge(mid)){

                 low=mid;

             }

             else{

                high=mid;

             }

         }

         printf("%.0f\n",mid*);

     }

 }

所以我们二分 L（0,1）

秒客网

POJ 2976（01分数划分+二分）

相关文章