P11176 [ROIR 2018 Day1] 提高成绩 题解

· · 题解

解题思路

观察发现，如果需要满足最终成绩大于等于 4，那么答案至少为 3.5。

很明显答案具有单调性，所以可以直接上二分。对于每个 mid，我们判断 \frac{2a + 3b + 4c + 5mid}{a + b + c + mid} 是否大于等于 3.5，如果是，那么 r = mid，否则 l = mid。最后输出 l 即可。

你以为这样就完了吗？还有很多问题的。建议看完下文。

死亡回放

为了方便吐槽，先放上完整代码。

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a, b, c;
inline bool check(int number5) {
    long double t = (a * 2 + b * 3 + c * 4 + number5 * 5);
    t /= (a + b + c + number5);
    if (t >= 3.5)
        return true;
    return false;
}
signed main() {
    cin >> a >> b >> c;
    int l = 0, r = 1e18;
    while (l < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l;
    return 0;
}

这题什么玩意，专门卡二分是吧，精度卡得死死的。开 double 会 WA，于是我开了 long double。但是开了 long double 后，long double t = (a * 2 + b * 3 + c * 4 + number5 * 5) * 1.0 / (a + b + c + number5); 会 WA 掉，但是写成：

long double t = (a * 2 + b * 3 + c * 4 + number5 * 5);
t /= (a + b + c + number5);

就能 AC。。。最后还需要注意 l = 0，假如一开始他的成绩已经大于 4 了，我们不需要再考 5 分了。

由于本蒟蒻不会推式子，所以调了半个小时的二分。。。