vjudge-link

题目大意：两个二元组 $a_i,b_i$，选出一个子序列使得 $100\frac{\sum a_i}{\sum b_i}$ 最大。

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
typedef double dd;
typedef long long ll;

const int N=1e5+10;

int n,k;
int ai[N],bi[N];
dd ci[N];

bool check(dd mid)
{
	for(int i=1;i<=n;i++)
		ci[i]=(dd)ai[i]-mid*(dd)bi[i];
	sort(ci+1,ci+1+n,greater<dd>());
	dd sum=0;
	for(int i=1;i<=n-k;i++) sum+=ci[i];
	return sum>=0;
}

int main()
{
	while(scanf("%d%d",&n,&k)!=EOF&&n&&k)
	{	
		for(int i=1;i<=n;i++)
			scanf("%d",&ai[i]);
		for(int i=1;i<=n;i++)
			scanf("%d",&bi[i]);
		dd l=0,r=1;
		while(r-l>1e-4)
		{
			dd mid=(l+r)/2;
			if(check(mid)) l=mid;
			else r=mid;
		}
		printf("%.0lf\n",l*100.0);
	}
	return 0;
}