POJ2976——Dropping tests（0/1分数规划）

传送门

最简单的分数规划

对于最终答案ans，有

$ans=frac{Σa_i*100}{Σb_i}$

则

$Σb_i*ans=Σa_i*100$

则

$Σ(b_i*ans-a_i*100)=0$

那么我们二分check就可以了

#include<cstring> 
#include<algorithm>
#include<iostream>
#include<cmath>
#include<cstdlib>
#include<stdio.h>
#include<cstdio>
using namespace std;
#define eps 1e-9
double a[1005],b[1005],c[1005];
int n,k;
inline int read(){
    char ch=getchar();
    int res=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
int main(){
    n=read(),k=read();
    while(n!=0){
        for(int i=1;i<=n;i++){
            scanf("%lf",&a[i]);
        }
        for(int i=1;i<=n;i++){
            scanf("%lf",&b[i]);
        }
        double l=0,r=100;
        while(l+eps<r){
            double mid=(l+r)/2;
            for(int i=1;i<=n;i++){
                c[i]=a[i]*100-b[i]*mid;
            }
            sort(c+1,c+1+n);
            double trt=0;
            for(int i=n;i>k;i--){
                trt+=c[i];
            }
            if(trt>eps) l=mid;
            else r=mid;
            }
        printf("%.0lf
",l);
        n=read(),k=read();
    }
}