題意:
給定n個(gè)二元數(shù),選取n-k個(gè)二元組合,使得sigma(a[i])/sigma(b[i])最大.
思路:
所以這就是最裸的0-1分?jǐn)?shù)規(guī)劃題,直接上模板,注意讀入時(shí)不要用cin,應(yīng)該用scanf,否則會(huì)超時(shí),我也不知道呀.
#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; //二分的范圍你可以試著確定,根據(jù)題意來(lái).這里題目中時(shí)保證了分母比分子大,
//所以答案應(yīng)該時(shí)不會(huì)超過(guò)1的.（當(dāng)然大點(diǎn)也行）
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時(shí)就要減小sum,故L右移,就可以把
//sum減小.因?yàn)楦鶕?jù)推論,當(dāng)sum越接近0時(shí),答案越最優(yōu).
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
*/
