题解：P12519 「MSTOI-R1」热开水

c_y_y · 2025-05-18 11:01:03 · 题解

P12519 「MSTOI-R1」热开水 题解

题面的一切指向了某 P 开头的音游~

注意到 b_i 是个正数，

因此第二天一个曲目的 rks 一定不小于第一天。因此发现总 rks 随天数增加而单调不降。本题具有单调性，考虑二分。

如何实现 check() 函数呢？按题意模拟就好了~

但是有以下几个细节：

• 一个曲目的 acc \le 70\% 时，该区 rks 应为 0。
• 对于所有的计算结果后，都应保留两位小数。
• 记得初始化！！！

同时对于本题，笔者有以下的小优化可以使实现更简单：

• 记 b_0 为所有 acc = 100\% 的曲目中 rks 的最大值，b_i (1 \le i \le 4) 为最大的四个 rks。
  先将 b_i (1 \le i \le 4) 升序排列。当我们计算出一个新的 rks 时，如果其 rks > b_1 就将其替换，并在最后像插入排序一样保持 b 数组升序。注意 b_0 不参与排序。

• 由于 b 的长度很小，因此计算总 rks 时，可直接暴力求解；

Code

const int N = 1e5 + 10, mod = 998244353;
double rt2(double x) {
    int y;
    double z;
    x *= 100, y = x;
    z = y / 100.0;
    return z;
}
struct node {
    double a, b, c, rks;
}a[N];
double b[6], tb[6], m;
int n;
bool check(int k) {
    double rks = 0;
    memcpy(b, tb, sizeof tb);
    for (int i = 1; i <= n; i++) {
        double acc = min(100.0, a[i].a + (k-1) * a[i].b);
        if(acc <= 70) a[i].rks = 0;
        else {
            a[i].rks = rt2((acc-55.0) / 45.0);
            a[i].rks = rt2(a[i].rks * a[i].rks * a[i].c);
        }
        if(a[i].rks > b[1]) b[1] = a[i].rks;

        if(acc == 100.0) b[0] = max(b[0], a[i].rks);
        double rks = rt2((b[0] + b[1] + b[2] + b[3] + b[4]) / 5.0);
        if(rks >= m) return true;
        for (int j = 1; j <= 3; j++) {
            if(b[j] > b[j + 1]) swap(b[j], b[j + 1]);
            else break;
        }
    }
    return false;
}
int main() {
    cin.tie(0), cout.tie(0);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i].a >> a[i].b >> a[i].c;
    }
    cin >> b[1] >> b[2] >> b[3] >> b[4] >> b[0];
    sort(b + 1, b + 5);
    for (int i = 0; i <= 4; i++) tb[i] = b[i];

    int l = 0, r = 10010, ans = -1;
    while(l <= r) {
        int mid = l + r >> 1;
        if(check(mid)) ans = mid, r = mid - 1;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}

Others

本题暴力有 95 分。

Phi 好玩，都给我去打 Phi！