一道$0/1$规划裸题吧。
把柿子写出来是这个样子的
$$\frac{\sum_{i=1}^{n}a_i*x_i}{\sum_{i=1}^{n}b_i*x_i}*100$$
先忽略掉$100$的常数。
就是一个模版,那么就可以做了。
因为可以不选任意$k$个,把最小的$k$个踢掉就好了。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define eps -1e-6
using namespace std;
const int N=1005;
int a[N],b[N],n,k;double c[N];
void solve()
{
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;
for(int i=1;i<101;i++)
{
double mid=(l+r)/2;
for(int j=1;j<=n;j++)
c[j]=a[j]-mid*b[j];
sort(c+1,c+n+1);double ans=0;
for(int j=k+1;j<=n;j++)
ans+=c[j];
if(ans>eps)l=mid;
else r=mid;
}
printf("%d\n",(int)((l+r)*50+0.5));
}
int main()
{
while(scanf("%d%d",&n,&k)&&n+k)
solve();
return 0;
}
最后一次更新于2020-02-20
0 条评论