2018牛客多校05 A gpa (01分数规划)

发表于 | 更新于 | 分类于 ， | 评论数： | 阅读次数：

链接：https://www.nowcoder.com/acm/contest/143/A

一个人有n个成绩，然后现在他可以删掉其中至多k个，使得目标方程$\frac{\sum[s[i]c[i]}{\sum s[i]}$的值最大，问这个值可以是多少。

这题和POJ2976是很类似的，是用01分数规划可以解决的问题。01分数规划可以看做是一种思想，可以用二分查找实现。针对这一道题，我们希望让目标方程尽可能大，于是可以假设：
$$
\frac{\sum[s[i]c[i]}{\sum s[i]} \geq L
$$
移项后得：
$$
\sum{s_ic_i-L×s_i}\geq0
$$
于是我们可以二分$L$，对该式中的$s_ic_i-L×s_i$进行计算并排序，删掉最小的k个后，查看是否满足题意。当收敛时，即$L$近似为式子的最大值。

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
#include <bits/stdc++.h>
using namespace std;
 
const double eps = 1e-9;
const int maxn = 101000;
int n, k, m;
int s[maxn], c[maxn];
double d[maxn];
 
bool ok(double L) {
  for(int i = 1; i <= n; i++) d[i] = (double)(s[i] * c[i]) - L * (double)s[i];
  sort(d+1, d+n+1);
  double tot = .0;
  for(int i = k+1; i <= n; i++) {
    tot += d[i];
  }
  return tot > 0;
}
 
signed main() {
  // freopen("in", "r", stdin);
  while(~scanf("%d%d",&n,&k)) {
    for(int i = 1; i <= n; i++) scanf("%d", &s[i]);
    for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
    double lo = .0, hi = 1e3;
    double ret = .0;
    while(hi - lo > eps) {
      double mid = (lo + hi) / 2.0;
      if(ok(mid)) lo = mid;
      else hi = mid;
    }
    printf("%.11f\n", lo);
  }
  return 0;
}