B. Hourglass

时间限制：1 秒
内存限制：256 兆字节

问题描述

瓦迪姆的沙漏可以测量 $s$ 分钟。他将其翻转过来，计时开始。之后，每隔 $k$ 分钟，瓦迪姆就会再次翻转他的沙漏。即使沙子仍在流动，他也会这样做。另外，如果沙子已经流完，但还需要等待一段时间才会到达下一次翻转时刻，瓦迪姆会等待到规定的时间，然后才翻转沙漏。每次翻转被视作瞬间完成。

然而，瓦迪姆需要在 $m$ 分钟后离开去办事，并且他将停止翻转沙漏（但如果瓦迪姆需要在最后一分钟翻转沙漏，他仍然会执行这次翻转）。请确定在瓦迪姆离开后，沙子还会继续流动多少分钟。

输入格式

输入包含多个测试用例。第一行包含一个整数 $t$ ($1 \le t \le 10^4$) —— 测试用例的数量。接下来的行描述每个测试用例。

每个测试用例仅有一行，包含三个整数 $s$, $k$, 和 $m$ —— 分别表示沙漏测量的分钟数、沙漏每隔多少分钟被翻转一次、以及瓦迪姆将在多少分钟后离开 ($1 \le s, k, m \le 10^9$)。

输出格式

对于每个测试用例，输出在瓦迪姆离开后，沙子还会继续流动多少分钟。

样例输入

6
8 8 12
5 10 17
12 2 3
16 7 7
1 1 10
2 60 15

样例输出

4
0
1
7
1
0

样例说明

• 第一个测试用例 s=8, k=8, m=12：瓦迪姆会在沙子刚好流完时（第8分钟）翻转沙漏，再经过4分钟后（第12分钟）离开，此时沙漏中还有4分钟的沙子待流，因此答案为 4。
• 第二个测试用例 s=5, k=10, m=17：瓦迪姆在第10分钟翻转沙漏，之后沙子需要流5分钟（至第15分钟流完），瓦迪姆在第17分钟离开，此时沙子早已流完，因此答案为 0。
• 第三个测试用例 s=12, k=2, m=3：在第一次翻转前（第2分钟），沙子已流了2分钟。翻转后，这2分钟的沙子会继续流。再过1分钟（第3分钟）瓦迪姆离开，此时沙漏中还有1分钟的沙子待流，因此答案为 1。
• 第四个测试用例 s=16, k=7, m=7：在第7分钟第一次翻转前，沙子已流了7分钟。瓦迪姆翻转后立即离开，因此翻转后沙漏中还有7分钟的沙子待流，答案为 7。
• 第五个测试用例 s=1, k=1, m=10：这是一个模拟过程，最终答案为 1。
• 第六个测试用例 s=2, k=60, m=15：在瓦迪姆离开前（15分钟）他从未翻转过沙漏（因为 $k=60 > m$），且初始沙子只有2分钟，早已在第2分钟流完，因此答案为 0。

这是一份针对 CF 2184 B - Hourglass 的算法总结笔记。这道题看似简单，实则包含了一个物理过程的循环规律，非常容易因为思维定势而 WA。

---

算法笔记：CF 2184 B - Hourglass

算法/数学 #算法/模拟 #题目/Codeforces #易错点

1. 题目本质

模拟一个沙漏在时间 $m$ 时的剩余沙量。

• 总容量：$s$

• 翻转周期：$k$

• 截止时间：$m$

核心难点在于：沙漏的初始状态在不同轮次是变化的，存在周期性。

2. 核心逻辑与分类讨论

我们需要比较沙漏总容量 $s$ 与翻转间隔 $k$ 的关系：

情况 A：$s \le k$（小沙漏，大周期）

• 物理过程：

  • 开始时沙漏有 $s$。

  • 因为 $s \le k$，在下一次翻转前，沙子一定能漏完。

  • 翻转瞬间，底部的 $s$ 全部翻到上面。

• 结论：每一轮开始时，沙漏上方都是满的 ($s$)。

• 公式：

  $$\text{Ans} = \max(0, s - (m \% k))$$

情况 B：$s > k$（大沙漏，小周期）

这是最容易错的地方。沙子永远漏不完，会在两个状态间循环。

• 第 0 轮 (偶数轮)：

  • 开始状态：上方 $s$，下方 $0$。

  • 经过 $k$ 分钟：漏掉 $k$。

  • 结束状态：上方 $s-k$，下方 $k$。

  • 若此时停止：剩余 $s - (m\%k)$。

• 第 1 轮 (奇数轮)：

  • 翻转瞬间：下方 $k$ 翻到上方。

  • 开始状态：上方 $k$，下方 $s-k$。

  • 经过 $k$ 分钟：漏掉 $k$（因为 $k < s$，肯定够漏）。

  • 结束状态：上方 $0$，下方 $s$。

  • 若此时停止：剩余 $k - (m\%k)$。

• 第 2 轮：

  • 翻转瞬间：下方 $s$ 翻到上方。

  • 状态回归到第 0 轮。

• 结论：状态以 $2k$ 为周期循环。

  • 偶数轮 ($m/k$ is even)：初始视为 $s$。

  • 奇数轮 ($m/k$ is odd)：初始视为 $k$。

3. 你的踩坑记录 (Post-Mortem)

[!WARNING] 错误思维

你之前的代码逻辑是：if (s >= k) ans = k - m % k;

错误原因：你默认了“只要沙漏够大，每次翻转上来的一定是 $k$”。

事实是：

• 第一次翻上来的是 $k$（对）；

• 第二次翻上来的是 $s$（错）；

• 第三次又是 $k$...

  你忽略了偶数轮次会把积攒在底部的剩余沙子($s-k$)也一起翻回来，导致偶数轮其实是满油状态。

4. 黄金代码模板

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

void solve(){
    LL s, k, m;
    cin >> s >> k >> m;

    // 情况 1: 沙漏容量小，每轮都能漏空并回满
    if (s <= k) {
        cout << max(0LL, s - m % k) << endl;
    } 
    // 情况 2: 沙漏容量大，形成 2k 的循环周期
    else {
        LL round = m / k;      // 当前是第几轮
        LL cur_time = m % k;   // 当前轮进行了多久

        if (round % 2 == 0) {
            // 偶数轮 (0, 2, 4...)：起始沙量为 s
            cout << s - cur_time << endl;
        } else {
            // 奇数轮 (1, 3, 5...)：起始沙量为 k
            // 注意：因为 s > k，且 cur_time < k，这里肯定不会减成负数
            cout << k - cur_time << endl;
        }
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
    return 0;
}

5. 一句话总结

做周期性模拟题时，千万不要只看前两步，至少要手动模拟到状态复原（回到初始态）为止，确认循环节长度是 $k$ 还是 $2k$。