B4079 [CSP-X2019 山东] 金币

chen_zhe · 2024-12-15 20:44:44 · 题解

欢迎报名洛谷网校，期待和大家一起进步！

本题考查模拟、数学与二分答案。

（模拟法） 以周为单位进行模拟，每次计算一周能获取多少枚金币并且累加求和，直到出现了拿了当前周金币之后金币总数 \geq n 的情况。遇到这种情况的时候，使用循环判断这一周的第几天时金币总数会超过 n。

在本题的数据范围内，该做法勉强可以通过，原因是这个数据范围下最大的周数大约是 5 亿周，答案不会特别大。但是这个做法在当时的 CSP-X 2019 可能无法通过。需要注意，相关的变量都需使用 long long 类型。

参考代码（部分）：

while (true) {
    if (week * 7 + cnt >= n) {
        int t = 0;
        while (week * t + cnt < n)
            t++;
        cout << day + t << endl;
        break;
    } else {
        cnt += 7 * week;
        week++;
        day += 7;
    }
}

（二分答案法） 该做法会显著更优，需要读者了解二分答案这一算法。

实际上，对于一个日期 x，在这个日期以及之前能拿到多少个金币是可以被计算的。这是可以通过数学计算简单获取的：

• 已经经过的完整的周数：y=\lfloor \dfrac{x}{7} \rfloor（即 x / 7）；
• 在完整的周内，一共可以获得：7\times 1+7\times 2+7\times 3+\dots+7\times y 枚金币。
  • 根据等差数列求和公式，可以写为 7\times \dfrac{y(y+1)}{2} 枚金币。
• 还有 x \bmod 7（x % 7）天是在第 (y+1) 周，因此可以获得 (y+1)\times (x\bmod 7) 枚金币。

因此总共的获得金币枚数是：7\times \dfrac{y(y+1)}{2}+(y+1)\times (x\bmod 7)。

但是显然我们不能直接枚举每一天，因为天数可能会过多，达到 30 亿天左右。但是，随着天数的增加，拿到的金币是不断增多的。这种单调性预示着本题是可以二分答案的。

具体而言，二分在第几天可以获得总计 n 枚金币，二分的判断过程就是统计得到的金币是否 \geq n（使用上面的数学公式快速计算），若是则让二分的右区间左移，否则让二分的左区间右移。

经过测试 n=999\,999\,999\,999\,999\,999 的情况，此时答案为 3\,741\,657\,384，右边界应当不低于这个数字。但是若右边界过大，运算过程就非常容易超过 long long 类型乃至 unsigned long long 类型的表达上限。在代码中采用了 4\times 10^9 作为右边界。

参考代码：

bool check(long long mid) { //mid：天数
    long long x = mid / 7; //计算过了多少个整的周
    long long cnt = 7 * (1 + x) * x / 2; //计算完整的周内获得的金币数
    cnt += (x + 1) * (mid % 7); //计算剩余的天数获得的金币数
    return cnt >= n;
}

while (l <= r) {
    long long mid = (l + r) / 2;
    if (check(mid)) {
        ans = mid;
        r = mid - 1;
    } else
        l = mid + 1;
}