题解：AT_abc013_3 [ABC013C] 節制

残阳如血 · 2025-02-06 12:43:28 · 题解

参考了官方题解的思路。

100 pts

solution

首先，容易发现一个性质：

最好将用餐的时间放到开始几天。

证明如下：

假设当前饱食度为 h'，用一个补充 t 饱食度的餐，不吃饭每天减 e 点饱食度

• 当先用餐时，最终饱食度为 h'+t-e；
• 当后用餐时，最终饱食度为 h'-e+t；

当 h'-e<0 时，“后用餐”的方案就失效了。 当 h'+t-e<0 时，显然两种方案都失效了。

所以“先用餐”的方案成功概率更大，故应当在前几天用餐。

假设 x 天吃普通餐，y 天吃简朴餐，则 n-x-y 天不用餐。

那么此时最后一天的饱食度即为 h+bx+dy-e(n-x-y)，要求其 >0（可见 讨论）。

枚举 x,y 并判断，就可以解决了。

时间复杂度为 O(n^2)，可以通过 n\le10^3 的数据。

code

record

#include <bits/stdc++.h>
using lint = long long;

lint ans = 1e18, n, h, a, b, c, d, e;

int main() {
    std::cin >> n >> h >> a >> b >> c >> d >> e;

    for (int x = 0; x <= n; ++x) {
        for (int y = 0; y <= n - x; ++y) {
            if (h + b * x + d * y - e * (n - x - y) > 0) {
                ans = std::min(ans, a * x + c * y);
                break;
            }
        }
    }

    std::cout << ans << std::endl;
    return 0;
}

101 pts

solution

考虑仅枚举 x，能否 O(1) 或者 O(\log n) 算出最小的可以满足条件的 y 呢？

推式子：

故可以 O(1) 根据 x 计算 y 的值。

需要注意，当算出 y<0 时，需要将 y 置为 0。

时间复杂度为 O(n)，可以通过 n\le5\times10^5 的数据。

code

record

#include <bits/stdc++.h>
using lint = long long;

lint ans = 1e18, n, h, a, b, c, d, e;

int main() {
    std::cin >> n >> h >> a >> b >> c >> d >> e;

    for (lint x = 0; x <= n; ++x) {
        lint y = floor(1.0 * (e * n - b * x - e * x - h) / (d + e)) + 1;
        if (y < 0) y = 0;

        ans = std::min(ans, a * x + c * y);
    }

    std::cout << ans << std::endl;
    return 0;
}