自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 21:16:56，当前版本为作者最后更新于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;
}