Dropping tests

POJ

题意：给定n个二元组(a,b)，扔掉k个二元组，使得剩下的a元素之和与b元素之和的比率最大.

分析：求(sum_{i=1}^{n-k}frac{a_i}{b_i})最大.分数规划板子题.设(mid=sum_{i=1}^{n-k}frac{a_i}{b_i}),则题目转化为(sum_{i=1}^{n-k}(a_i-mid*b_i)>=0),二分答案判断就好了.

//#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read(){
   int s=0,w=1;char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9'){s=s*10+ch-'0';ch=getchar();}
   return s*w;
}
int n,k,a[1005],b[1005];
double eps=1e-6,val[1005];
inline bool check(double mid){
    for(int i=1;i<=n;i++)val[i]=a[i]-mid*b[i];
    sort(val+1,val+n+1);
    double sum=0.0;int cnt=0;
    for(int i=n;i;i--){
		sum+=val[i];
		cnt++;if(cnt==k)break;
    }
    if(sum>=0)return 1;
    return 0;
}
int main(){
    while(1){
		n=read(),k=read();if(n==0&&k==0)return 0;
		k=n-k;
		for(int i=1;i<=n;i++)a[i]=read();
		for(int i=1;i<=n;i++)b[i]=read();
		double l=0,r=1e9,mid;
		while(l+eps<r){
	    	mid=(l+r)/2.0;
	    	if(check(mid))l=mid;
	    	else r=mid;
		}
		printf("%.0lf
",l*100);//注意一下输出
    }
    return 0;
}