B4079 [CSP-X2019 山东] 金币

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

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

（模拟法） 以周为单位进行模拟，每次计算一周能获取多少枚金币并且累加求和，直到出现了拿了当前周金币之后金币总数

\geq n

的情况。遇到这种情况的时候，使用循环判断这一周的第几天时金币总数会超过

n

。

在本题的数据范围内，该做法勉强可以通过，原因是这个数据范围下最大的周数大约是

5

亿周，答案不会特别大。但是这个做法在当时的 CSP-X 2019 可能无法通过。需要注意，相关的变量都需使用 long long 类型。

参考代码（部分）：

CPP

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 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

作为右边界。

参考代码：

CPP

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;
}

B4079 [CSP-X2019 山东] 金币

文章操作

相关推荐

评论

B4079 [CSP-X2019 山东] 金币