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