思路

01分数规划模板题。

代码

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
//#define int long long
using namespace std;
const int N=1007;
const int mod=1e9+7;

int n,k;
double a[N],b[N],c[N];

bool check(double ans){
	for(int i=1;i<=n;i++){
		c[i]=a[i]-b[i]*ans;
	}
	sort(c+1,c+1+n);
	double res=0;
	for(int i=n;i>k;i--){
		res+=c[i];
	}
	if(res>=0) return true;
	return false;
} 

signed main(){
	while(cin>>n>>k){
		if(n==0&&k==0) break;
		for(int i=1;i<=n;i++) cin>>a[i];
		for(int i=1;i<=n;i++) cin>>b[i];
		double l=0,r=inf,mid;
		while(r-l>1e-6){
			mid=(l+r)/2;
			if(check(mid)) l=mid;
			else r=mid; 
		}
		cout<<int(l*100+0.5)<<"\n";
	}
	return 0;
}