题目的意思是你现在有n场测试,每场测试的成绩总共有b个题目,你对了a个题目,然后你可以选择放弃k个测试,选择剩下的所有测试来作为你的总分数,总分数定义为∑ai/∑bi。请计算你能获得的最大分数。


明显的01分数规划模板题,我们令∑ai/∑bi>=x,所以有∑ai-x*∑bi>=0;

对每场测试进行计算然后排序选择除掉k个之后剩下的和然后不断判断就好了。


01分数规划不会?不如看看之前文章的分析:传送门-01分数规划介绍


地址:http://poj.org/problem?id=2976

代码:

StatusAccepted
Time63ms
Memory212kB
Length816
LangC++


#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn=1005;
const double L=0, R=1;
const double eps=1e-4;
int a[maxn], b[maxn];
double add[maxn];
int n, k;
bool check(double x){
    for(int i=0;i<n;i++){
        add[i]=a[i]*1.0-x*b[i]*1.0;
    }
    sort(add, add+n);
    double sum=0;
    for(int i=n-1;i>=k;i--)sum+=add[i];
    if(sum>=0)return 1;
    return 0;
}
int main()
{
    while(~scanf("%d%d", &n, &k)&&(n||k)){
        for(int i=0;i<n;i++){
            scanf("%d", &a[i]);
        }
        for(int i=0;i<n;i++){
            scanf("%d", &b[i]);
        }
        double l=L, r=R;
        while(r-l>=eps){
            double mid=(l+r)/2;
            if(check(mid))l=mid;
            else r=mid;
        }
        printf("%.0lf\n", 100*l);
    }
    return 0;
}