题解

问题分析

核心是分析 Alice 和 Bob 拿瓜的博弈过程，关键在于理解“拿瓜后需花费同等时间吃掉才能再次拿瓜”以及“Alice 反应更快”这两个规则对拿瓜顺序的影响： $1$. 每次拿瓜后，吃瓜时间会阻塞后续拿瓜操作，反应快的 Alice 会优先完成吃瓜并获得下一次拿瓜机会； 2. 两人的目标都是最大化自身吃到的瓜量，因此会采取最优策略阻止对方获取更多瓜。

关键结论

通过博弈分析可得出核心策略：

• 若 Alice 首次拿瓜能占据绝对优势（即剩余瓜量≤她的吃瓜时间），则可独占剩余瓜；
• 最优策略为 Alice 首次拿瓜量尽可能多，使得 Bob 即使拿完剩余瓜，也会因吃瓜时间更长而无法干扰 Alice 后续拿瓜。

最终推导得出：

• 当 ( n \leq L ) 时，Alice 可一次性拿完所有瓜，答案为 ( n )；
• 当 ( n > L ) 时，Alice 最多能拿 ( \lceil \frac{n}{2} \rceil ) 单位的瓜（因 Bob 会阻止其拿更多，双方最终接近均分，但 Alice 因反应快可多拿 1 单位）。

实现代码

#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        ll n, L;
        cin >> n >> L;
        if (n <= L) {
            cout << n << '\n';
        } else {
            cout << (n + 1) / 2 << '\n';
        }
    }
    return 0;
}

算法标签

• 博弈论：双方为最大化自身利益采取最优策略，属于零和博弈问题；
• 贪心算法：Alice 首次拿瓜选择最优数量，直接奠定全局优势；
• 数学推导：通过分析拿瓜和吃瓜的时间关系，得出简洁的数学结论。

复杂度分析

• 时间复杂度：( O(T) )，每组数据仅需一次判断和计算，适合大规模输入（( T \leq 10^5 )）；
• 空间复杂度：( O(1) )，仅使用常数额外空间，效率极高。

该解法充分利用了博弈的最优策略和数学规律，能够高效处理题目中可能的超大数值范围（( n, L \leq 10^{18} )）。