题解：P15528 [ROIR 2015 Day 2] forest 伐木

a_super_Gambler · 2026-03-07 10:09:20 · 题解

题目传送门。

前置知识：二分。

题意概述

德米特里和费多尔要砍 X 棵树，两人的砍伐规则如下：

• 德米特里每天砍伐 A 棵树，每 K 天休息。
• 费多尔每天砍伐 B 棵树，每 M 天休息。

求两人需要多少天才能砍完所有的树。

思路

直接枚举会超时，因为 X 高达 10^{18}，所以考虑二分。

边界值 l = 1，r = 10^{18}，因为最好的情况下只需一天就可以了，最坏的情况下两人每天只砍伐一棵树，隔一天休息一天，过 10^{18} 天也能砍完。

至于决策函数，设 day 表示过了 day 天，该怎么判断过了 day 天后是否砍完了所有的树？不难想到， 德米特里每 K 天休息，于是他实际在砍树的天数只有 day - \lfloor day / K \rfloor 天，费多尔同理。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, k, b, m, x;
bool check(ll day){
    return (__int128)(day - day / k) * a + (__int128)(day - day / m) * b >= x;//用__int128是因为 long long 会溢出
}
int main(){
    cin >> a >> k >> b >> m >> x;
    ll l = 1, r = 1e18, ans;
    while (l <= r){
        ll mid = l + (r - l) / 2;//(l + r) / 2的另一种写法，这种写法可以避免溢出
        if (check(mid)) r = mid - 1, ans = mid;
        else l = mid + 1;
    }
    cout << ans << endl;
    return 0;
}