牛客多校5 A-gpa（01分数规划）

gpa

链接：https://www.nowcoder.com/acm/contest/143/A
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
Special Judge, 64bit IO Format: %lld

题目描述

Kanade selected n courses in the university. The academic credit of the i-th course is s[i] and the score of the i-th course is c[i].

At the university where she attended, the final score of her is $\frac{\sum s[i]c[i]}{\sum s[i]}$

Now she can delete at most k courses and she want to know what the highest final score that can get.

输入描述:

The first line has two positive integers n,k

The second line has n positive integers s[i]

The third line has n positive integers c[i]

输出描述:

Output the highest final score, your answer is correct if and only if the absolute error with the standard answer is no more than 10

^-5

输入例子:

输出例子:

2.33333333333

-->

示例1

输入

复制

输出

复制

2.33333333333

说明

Delete the third course and the final score is

$\frac{2*2+3*1}{2+1}=\frac{7}{3}$

备注:

1≤ n≤ 10

⁵


0≤ k < n

1≤ s[i],c[i] ≤ 10

附01分数规划讲解：https://blog.csdn.net/hhaile/article/details/8883652

#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#include<math.h>

#include<algorithm>

#define MAX 100005

#define INF 0x3f3f3f3f

#define MOD 1000000007

using namespace std;

typedef long long ll;

double s[MAX],c[MAX],cnt[MAX];

int main()

{

    int n,k,i;

    scanf("%d%d",&n,&k);

    for(i=;i<=n;i++){

        scanf("%lf",&s[i]);

    }

    for(i=;i<=n;i++){

        scanf("%lf",&c[i]);

    }

    double l=,r=;

    while(r-l>0.000001){

        double mid=(l+r)/;

        for(i=;i<=n;i++){

            cnt[i]=s[i]*c[i]-mid*s[i];

        }

        sort(cnt+,cnt+n+);

        double fx=;

        for(i=k+;i<=n;i++){

            fx+=cnt[i];

        }

        if(fx>=) l=mid;

        else r=mid;

    }

    printf("%f\n",l);

    return ;

}

巴特西