Dropping tests

01分数规划,sort+二分即可。注意精度问题,这种四舍五入的问题一般都是两种处理方法:1、printf("%.0lf\n",ans);  2、printf("%d\n",(int)(ans+0.5));

#include<cstring>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
#define N 1010
double a[N],b[N],c[N];
int n,K;
int main()
{
    int i;
    double left,right,mid,sum;
    while(scanf("%d%d",&n,&K),n||K)
    {
        for(i = 1; i <= n; i++)
            scanf("%lf",&a[i]);
        for(i = 1; i <= n; i++)
            scanf("%lf",&b[i]);
        left = 0; right = 1;
        while(1)
        {
            if(fabs(left-right) < 0.0001) break;
            mid = (left+right)/2;
            for(i = 1; i <= n; i++)
                c[i] = a[i] - mid*b[i];
            sort(c+1,c+1+n); sum = 0;
            for(i = K+1; i <= n; i++)
                sum += c[i];
            if(sum > 0) left = mid;
            else right = mid;
        }
        left = left*100;
        printf("%.0f\n",left);
    }
    return 0;
}

Dropping tests

上一篇:【愚公系列】2021年12月 二十三种设计模式(六)-适配器模式(Adapter Pattern)


下一篇:【24】若所有参数皆需类型转换,请为此采用non-members函数