1429.[CSP-J 2021]分糖果

算法思路

1. 问题分析

题目要求在区间 [L, R] 中选择一个整数 k，使得经过多次减去 n 操作后（直到剩余糖果少于 n），剩余糖果数量（即 k mod n）最大。本质是求余数最大值问题，核心在于分析区间 [L, R] 与 n 的整数倍区间的关系。

2. 解决策略

• 情况1：若 L 和 R 位于同一个 n 的整数倍区间内（即 L // n == R // n），则最大余数为 R % n。
• 情况2：若 L 和 R 跨越多个整数倍区间（即 L // n != R // n），则必然存在某个 k 使余数达到最大值 n-1。
• 数学依据：余数具有周期性（周期为 n），当区间跨越完整周期时，必包含余数为 n-1 的值。

3. 复杂度分析

• 时间复杂度：O(1)，仅需常数次整数除法和取模运算。
• 空间复杂度：O(1)，仅使用固定数量的变量存储中间结果。

代码实现

C++解法

cpp
复制
1#include <iostream>
2using namespace std;
3
4int main() {
5    // 输入小朋友数n、糖果下界L、上界R
6    long long n, L, R;
7    cin >> n >> L >> R;
8    
9    // 判断L和R是否在同一整数倍区间
10    if (L / n == R / n) {
11        // 若在同一区间，最大余数为 R % n
12        cout << R % n;
13    } else {
14        // 若跨区间，最大余数为 n-1
15        cout << n - 1;
16    }
17    return 0;
18}

代码解释：

• 输入处理：直接读入三个整数 n, L, R。
• 核心逻辑：
  • L / n == R / n：判断是否在同一整数倍区间（整数除法）。
  • R % n：同一区间时，余数最大值在区间右端点 R 处。
  • n - 1：跨区间时，余数最大值恒为 n-1。
• 边界处理：题目保证 n ≤ L ≤ R，无需额外边界检查。

Python3解法

python
复制
1def main():
2    # 输入小朋友数n、糖果下界L、上界R
3    n, L, R = map(int, input().split())
4    
5    # 判断L和R是否在同一整数倍区间
6    if L // n == R // n:
7        # 若在同一区间，最大余数为 R % n
8        print(R % n)
9    else:
10        # 若跨区间，最大余数为 n-1
11        print(n - 1)
12
13if __name__ == "__main__":
14    main()

代码解释：

• 输入处理：使用 map 和 split 解析输入。
• 与C++差异：
  • Python 整数除法使用 //（C++自动向下取整）。
  • 无需显式类型声明，支持大整数运算。
• 关键逻辑：
  • L // n == R // n：等价于C++的整数除法比较。
  • R % n 和 n-1：余数计算逻辑与C++一致。

复杂度对比

1. 效率差异：
   • 时间复杂度：双语言均为 O(1)，性能无差异。
   • 空间复杂度：双语言均为 O(1)，仅需常数空间。
2. 选择建议：
   • C++：适合超大规模输入（10^18 级别），因Python大整数计算略慢。
   • Python：代码简洁，适合快速实现和较小数据范围（10^9 级别）。
3. 场景示例：
   • 竞赛中优先选择C++应对极端数据（如 n=10^18）。
   • 日常训练或笔试可用Python提升开发效率。