传送门： 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
| 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 分数规划的问题 (模板题)，自己之前在白书上看过，做到这题时忘了，多谢朱兄的提醒。
讲解
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;
}
|