[文章目录]
Description
就是给你n个物品，让你去掉k个，使得剩下的物品总的性价比最高。
裸分数规划问题。
假设最后的答案为L。那么就有L=其中，xi为0||1。考虑转化：令f(L)=。我们发现对于每一个ai,bi都是一个一次函数，并且对于x来说，当x增大的时候每一部分都是递减的，另外，当f(L)>0的时候说明，存在更优解。
那么我们进行贪心，每次累加最大前k个，又因为刚才说到说到的每一部分都是单调递减的，所以可以进行二分，当f(L)>0时增大L。当f(L)==0时,L即为所求。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int n,k,a[1010],b[1010];
double d[1010];
bool check(double x)
{
for(int i=1;i<=n;i++) d[i]=1ll*a[i]-x*b[i];
sort(d+1,d+n+1);
double sum=0;
for(int i=k+1;i<=n;i++) sum+=d[i];
return sum<0;
}
int main()
{
while(scanf("%d%d",&n,&k))
{
if(n==0&&k==0) break;
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
double l=0,r=1,mid; int t=30;
while(t--)
{
mid=(l+r)/2;
if(check(mid)) r=mid;
else l=mid;
}
printf("%.0lf\n",100*r);
}
return 0;
}