2018牛客网暑期ACM多校训练营(第五场)A gpa 01分数规划

传送门: 2018牛客网暑期ACM多样训练营(第五场)A gpa

Description

题目描述

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

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

输入描述:

1
2
3
4
5
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]

输出描述:

1
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

输入

1
2
3
3 1
1 2 3
3 2 1

输出

1
2.33333333333

说明

1
Delete the third course and the final score is

备注

1
2
3
4
5
1≤ n≤ 105

0≤ k < n

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

Solution

题意

大学里有n门课,每门课有着自己的学分,gpa的计算公式为 ${\sum{分数 * 学分} \over {\sum学分}}$, 现可以最多除去$k$门课成绩,问绩点最多可以达到多少。

思路

这题一看就不可以贪心。是一个01分数规划的问题(模板题),自己之前在白书上看过,做到这题时忘了,多谢朱兄的提醒。

讲解

markmarkmark

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn=1e5+7;
const double eps=1e-7;
int n,k;
double a[maxn];
double b[maxn];
int main()
{
while(cin>>n>>k)
{
if(n==0&&k==0)break;
for(int i=0;i<n;i++)
scanf("%lf",&b[i]);
for(int j=0;j<n;j++)
scanf("%lf",&a[j]);
for( int j = 0; j < n; ++j ) {
a[j] = a[j] * b[j];
}

double L=1.0;
double R=1000.0;
double mid;

double t[maxn];

while(R-L>eps)
{
mid=(R+L)*1.0/2;

for(int i = 0; i < n; i++)
t[i] = a[i] - mid * b[i];
sort(t, t + n);
double sum = 0;
for(int i = k; i < n; i++)
sum += t[i];

if(sum>0)
L=mid;
else
R=mid;
}
printf("%.5f\n",mid);
break;
}
return 0;
}
❤采之欲遗谁,所思在远道。❤
0%