题目链接:http://poj.org/problem?id=2976
题意:
共有n场考试,每场考试你得的分数为a[i],总分为b[i]。
你可以任意去掉k场考试。
问你最大的 100.0 * ( ∑ a[i] / ∑ b[i] )的值。(四舍五入)
题解:
相当于从n场考试中选n-k场。
二分:
二分最大答案 ∑ a[i] / ∑ b[i] >= L
即:∑ a[i] - ∑(b[i]*L) >= 0
check函数:
求数组val[i] = a[i] - b[i]*L
将val排序。
取最大的n-k个val[i],求和为sum。
若sum >= 0则满足条件,lef = mid.
否则rig = mid.
AC Code:
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define MAX_N 1005
#define INF 10000000
#define EPS 0.000001 using namespace std; int n,m;
double ans;
double a[MAX_N];
double b[MAX_N];
double val[MAX_N]; void read()
{
for(int i=;i<n;i++)
{
scanf("%lf",&a[i]);
}
for(int i=;i<n;i++)
{
scanf("%lf",&b[i]);
}
} bool is_legal(double x)
{
for(int i=;i<n;i++)
{
val[i]=a[i]-x*b[i];
}
sort(val,val+n);
double sum=;
for(int i=n-;i>=m;i--)
{
sum+=val[i];
}
return sum>=;
} void solve()
{
double lef=;
double rig=;
while(rig-lef>EPS)
{
double mid=(lef+rig)/2.0;
if(is_legal(mid)) lef=mid;
else rig=mid;
}
ans=lef;
} void print()
{
printf("%.0f\n",ans*100.0);
} int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
if(n== && m==) break;
read();
solve();
print();
}
}