NC17400 gpa

题目

题目描述

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}\)

示例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^5\)

\(0≤ k < n\)

\(1≤ s[i],c[i] ≤ 10^3\)

题解

思路

知识点：01分数规划。

删去 \(k\) 个课程，那剩下取 \(n-k\) 个课程。答案的可行性函数符合单调性，且答案是唯一零点，于是二分答案，有如下公式：

\[\begin{aligned}
\frac{\sum s[i]c[i]}{\sum s[i]} &\geq mid\\
\sum (s[i]c[i] - mid \cdot s[i]) &\geq 0
\end{aligned}
\]

因此每次检验对 \(s[i]c[i]-mid\cdot s[i]\) 从大到小排序，取前 \(n-k\) 个加和，观察是否满足不等式，来决定舍弃区间。

注意精度开大一次方。

时间复杂度 \(O(n \log n + k)\)

空间复杂度 \(O(n)\)

代码

#include <bits/stdc++.h>

using namespace std;

double s[100007], c[100007], sc[100007];

int n, k;

bool check(double mid) {

    for (int i = 0;i < n;i++) sc[i] = s[i] * c[i] - mid * s[i];

    sort(sc, sc + n, [&](double a, double b) {return a > b;});

    double sum = 0;

    for (int i = 0;i < n - k;i++) sum += sc[i];

    return sum >= 0;

}

int main() {

    std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    cin >> n >> k;

    for (int i = 0;i < n;i++) cin >> s[i];

    for (int i = 0;i < n;i++) cin >> c[i];

    double l = 0, r = 1e3;

    while (r - l >= 1e-6) {

        double mid = (l + r) / 2;

        if (check(mid)) l = mid;

        else r = mid;

    }

    cout << fixed << setprecision(6) << l << '\n';

    return 0;

}

巴特西

NC17400 gpa

NC17400 gpa

题目

备注:

题解

思路

代码

最新文章

热门文章