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
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,kThe 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
示例1
输入
复制
3 1
1 2 3
3 2 1
输出
复制
2.33333333333
说明
Delete the third course and the final score is
备注:
1≤ n≤ 10
5
0≤ k < n1≤ s[i],c[i] ≤ 10
3
附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=
1;i<=n;i++
){
scanf("%lf",&
s[i]);
}
for(i=
1;i<=n;i++
){
scanf("%lf",&
c[i]);
}
double l=
0,r=
1000;
while(r-l>
0.000001){
double mid=(l+r)/
2;
for(i=
1;i<=n;i++
){
cnt[i]=s[i]*c[i]-mid*
s[i];
}
sort(cnt+
1,cnt+n+
1);
double fx=
0;
for(i=k+
1;i<=n;i++
){
fx+=
cnt[i];
}
if(fx>=
0) l=
mid;
else r=
mid;
}
printf("%f\n",l);
return 0;
}
转载于:https://www.cnblogs.com/yzm10/p/9408966.html
