【CSP-J 2021】分糖果题（洛谷P7909）解题思路与代码解析

15303105423

一、题目解读

2021年CSP-J分糖果问题（洛谷P7909）要求计算在给定的糖果数量n及区间范围L和R下，糖果分配后剩余糖果数的最大值。核心目标是通过数学逻辑确定R mod n的最大可能余数，需考虑区间跨度的边界条件。

二、解题思路

通过以下逻辑解题：

1. 计算R mod n得到初始余数max_mod。

2. 判断R/n与L/n的商是否相同：

    若不同（即R与L跨越n的倍数区间），则最大余数为n-1（因R可取值接近n的倍数，余数接近n-1）。

    若相同，则最大余数即为max_mod。

该思路基于对区间边界与取模运算特性的深刻理解，避免了复杂循环，实现O(1)时间复杂度。

三、解题步骤

1. 输入n、L、R参数。

2. 计算max_mod = R % n。

3. 通过if条件判断：

    若R/n > L/n，说明区间跨越倍数边界，输出n-1。

    否则输出max_mod。

4. 结束程序。

关键步骤在于利用数学关系简化计算，避免枚举所有可能性。

四、代码与注释

1. #include <iostream>  
   
2. using namespace std;  
   
3. 
   
4. int main() {  
   
5.     int n, L, R;  
   
6.     cin >> n >> L >> R;  
   
7. 
   
8.     // 计算R mod n的最大可能值  
   
9.     int max_mod = R % n;  
   
10. 
    
11.     // 计算最大的可能余数  
    
12.     if (R / n > L / n) {  
    
13.         // 如果R和L不在同一个n的倍数区间内，最大余数就是n-1  
    
14.         cout << n - 1 << endl;  
    
15.     } else {  
    
16.         // 否则最大余数就是R mod n  
    
17.         cout << max_mod << endl;  
    
18.     }  
    
19. 
    
20.     return 0;  
    
21. }

复制代码

注释：代码通过简洁的if条件直接判定结果，无需额外循环或递归，体现了竞赛中高效解题的思维。

五、总结

本文通过分析CSP-J分糖果题的数学本质，结合作者代码的简洁逻辑，揭示了取模运算与区间边界的关系。关键点在于识别R与L是否处于同一n的倍数区间，从而直接确定最大余数。该解法为算法竞赛中的数学推导类问题提供了高效范式，建议读者结合实例深入理解边界条件判断的技巧。

来源：【CSP-J 2021】分糖果题（洛谷P7909）解题思路与代码解析