题意:
给定n个二元数,选取n-k个二元组合,使得sigma(a[i])/sigma(b[i])最大.
思路:
所以这就是最裸的0-1分数规划题,直接上模板,注意读入时不要用cin,应该用scanf,否则会超时,我也不知道呀.
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<set>
#include<queue>
#include<functional>
#include<vector>
#include<stack>
#include<map>
#include<cstdlib>
#define CLR(x) memset(x,0,sizeof(x))
#define ll long long int
#define PI acos(-1.0)
#define db double
#define mod 1000000007
using namespace std;
const int maxn=1e6;
const db eps=1e-7;
const int inf=1e9;
const ll INF=1e15;
db a[1005],b[1005],c[1005];
int main()
{
int n,k;
while(scanf("%d %d",&n,&k)!=EOF){
CLR(c);
if(n==0 && k==0)
break;
for(int i=0;i<n;i++)
scanf("%lf",&a[i]);
for(int i=0;i<n;i++)
scanf("%lf",&b[i]);
db l=0.0;
db r=10.0; //二分的范围你可以试着确定,根据题意来.这里题目中时保证了分母比分子大,
//所以答案应该时不会超过1的.（当然大点也行）
db mid;
while(r-l>eps){
mid = (r+l)/2.0;
/*cout << l << " " << r << endl;
cout << mid << endl;*/
for(int i=0;i<n;i++)
c[i]= a[i]-mid*b[i];
sort(c,c+n);
db sum=0;
for(int i=k;i<n;i++)
sum+=c[i];
if(sum > 0) //目的是使sum不断逼近0.所以大于0时就要减小sum,故L右移,就可以把
//sum减小.因为根据推论,当sum越接近0时,答案越最优.
l=mid;
else
r=mid;
}
printf("%.0f\n",mid*100);
}
}
/*
3 1
5 0 2
5 1 6
4 2
1 2 7 9
5 6 7 9
0 0
*/
