CSP-J 2021 T1 Candy

力巴尔 · 2021-12-02 18:17:44 · 个人记录

CSP-J T1 Candy

这道题第一眼看肯定是暴力，然后很多人就打了如下代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, r, l, a = 0;
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &l, &r);
    for (long long i = r;i >= l;i--)
        a = max(a, i % n);
    printf("%lld", a);
    return 0;
}

那结果肯定是

稻花香里说丰年

听取WA声一片

啊呸，只会TLE

然后我就加了一点点优化：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, r, l, a = 0;
    freopen("candy.in", "r", stdin);
    freopen("candy.out", "w", stdout);
    scanf("%lld%lld%lld", &n, &l, &r);
    for (long long i = r;i >= l;i--)
    {
        a = max(a, i % n);
        if (a == n - 1)
            break;
    }
    printf("%lld", a); 
    return 0;
}

然而，温(yin)柔(xian)善(jiao)良(zha)的CCF只给了你90分！

所以，暴力是不行的，这题一定要推公式！！！

由题可知，最优情况下会剩 (n - 1) 块糖果，但是，有时候我们可能最优的结果达不到 (n - 1) 块，那么就可以得出：在 l 到 r 之间的数越大，模 n 的值就越大。所以如果是这种情况，就直接拿 r 块糖果，结果一定是最优的。而其他情况的最优值就是拿 (n - 1) 块糖果。

从而得出以下代码：

#include <bits/stdc++.h>
using namespace std;
int main()
{
    long long n, l, r;
    cin>>n>>l>>r;
    cout<<min(r, l + (n - 1 - l % n)) % n;
    while(1)puts("我抄袭了力巴尔的代码！");
    return 0;
}