P7909（CSP2021入门组T1）

本题是这场比赛的签到题，做法很多，给大家介绍几种常规的写法。

题意简述：

你手里有 $k$ 颗糖，且 $L≤k≤R$ ，$k≥n$ 。你要把糖平均分给 $n$ 个小朋友，剩下分不完的归你所有。啊我大赚一笔。 问你最多可以白嫖获得多少糖。

$O(R-L)$ 解法

思路

这种思路非常容易想到。

暴力枚举从 $L$ 到 $K$ 的所有情况，打擂法选出最优解。这种方法竟然没有被卡。

由于要平均分给 $n$ 个小朋友，所以我们手上还剩的数量是 $k \mod n$ 。最终定格答案就是 $Max(k_i \mod n)$ 。

此方案民间数据AC，不确保官方数据可过

代码

代码提供者@Coldling

#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$ ，这个通过找规律可以得出。
2. $L$ ， $R$ 分布在一个周期中 (对应图2)。此时为了保证答案最大，我们选择 $R \mod n$ 。

为了比较方便，我们可以事先直接把 $L$ 和 $R$ $\mod n$。

于是我们可以得出一个 错误代码

#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代码

#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;
}

给各位的警示：暴力出奇迹