Solution to P7909
Chinshyo
2021-10-23 18:26:45
# [P7909（CSP2021入门组T1）](https://www.luogu.com.cn/problem/P7909)
本题是这场比赛的签到题，做法很多，给大家介绍几种常规的写法。
# 题意简述：
你手里有 $k$ 颗糖，且 $L≤k≤R$ ，$k≥n$ 。你要把糖平均分给 $n$ 个小朋友，剩下分不完的归你所有。~~啊我大赚一笔。~~ 问你最多可以~~白嫖~~获得多少糖。
# $O(R-L)$ 解法
### 思路
这种思路非常容易想到。
暴力枚举从 $L$ 到 $K$ 的所有情况，打擂法选出最优解。这种方法竟然没有被卡。
由于要平均分给 $n$ 个小朋友，所以我们手上还剩的数量是 $k \mod n$ 。最终定格答案就是 $Max(k_i \mod n)$ 。
**此方案民间数据AC，不确保官方数据可过**
### 代码
代码提供者@[Coldling](www.luogu.com.cn/user/233576)
```cpp
#include<bits/stdc++.h>
using namespace std;
int n,l,r,k,ans;
int main(){
cin>>n>>l>>r;
for(int i=l;i<=r;i++){
k=i;
ans=max(ans,k%n);
}
cout<<ans;
return 0;
}
```
# $O(1)$ 解法
### 思路
暴力枚举的方法完全是可以优化的。在枚举的过程中会产生**周期**。我们只要在这个周期内研究即可。
这边我们拿样例画图推柿子。
这两个图都是来源于样例中的数据，请参考样例阅读。从图中我们发现 $k_i \mod n(L≤k_i≤R)$ 的最大值有两种情况：
1. $L$ ， $R$ 分布在两个不同的周期中（对应图1）。此时的答案是 $n - 1$ ，这个通过找规律可以得出。
1. $L$ ， $R$ 分布在一个周期中 (对应图2)。此时为了保证答案最大，我们选择 $R \mod n$ 。
为了比较方便，我们可以事先直接把 $L$ 和 $R$ $\mod n$。
于是我们可以得出一个 **错误代码**
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
int n, l, r;
scanf("%d%d%d", &n, &l, &r);
else {
l = l % n;
r = r % n;
if(r < l) cout << n - 1 << endl;
else cout << r << endl;
}
return 0;
}
```
为什么会错呢，那是因为如果 $L$ 和 $R$ 分别在两个不同的周期且**相隔一个周期**时，经过 $mod$ 运算后可能会被作为 $R ≥ L$ 的情况处理。因此我们只需要加上**特判**即可 $\color{green} AC$ 。
### AC代码
```cpp
#include<bits/stdc++.h>
using namespace std;
int main() {
//freopen("candy.in", "r", stdin);
//freopen("candy.out", "w", stdout);
int n, l, r;
scanf("%d%d%d", &n, &l, &r);
if(r - l >= n) cout << n - 1 << endl;
else {
l = l % n;
r = r % n;
if(r < l) cout << n - 1 << endl;
else cout << r << endl;
}
return 0;
}
```
### 给各位的警示：暴力出奇迹
