信息学奥赛复赛复习12-CSP-J2021-01分糖果-模运算、余数、打擂台求最值、最大值、最小值
PDF文档回复:20241005
**1 P7909 [CSP-J 2021] 分糖果 **
[题目描述]
红太阳幼儿园有 n 个小朋友，你是其中之一。保证 n≥2
有一天你在幼儿园的后花园里发现无穷多颗糖果，你打算拿一些糖果回去分给幼儿园的小朋友们
由于你只是个平平无奇的幼儿园小朋友，所以你的体力有限，至多只能拿 R 块糖回去
但是拿的太少不够分的，所以你至少要拿 L 块糖回去。保证 n≤L≤R
也就是说，如果你拿了 k块糖，那么你需要保证 L≤k≤R
如果你拿了 k 块糖，你将把这 k 块糖放到篮子里，并要求大家按照如下方案分糖果：只要篮子里有不少于 n 块糖果，幼儿园的所有 n 个小朋友（包括你自己）都从篮子中拿走恰好一块糖，直到篮子里的糖数量少于 n 块。此时篮子里剩余的糖果均归你所有——这些糖果是作为你搬糖果的奖励
作为幼儿园高质量小朋友，你希望让作为你搬糖果的奖励的糖果数量（而不是你最后获得的总糖果数量！）尽可能多；因此你需要写一个程序，依次输入 n,L,R，并输出你最多能获得多少作为你搬糖果的奖励的糖果数量
[输入格式]
输入一行，包含三个正整数 n,L,R，分别表示小朋友的个数、糖果数量的下界和上界
[输出格式]
输出一行一个整数，表示你最多能获得的作为你搬糖果的奖励的糖果数量
[输入输出样例]
输入 #1
7 16 23
输出 #1
6
输入 #2
10 14 18
输出 #2
8
说明/提示
拿 k=20 块糖放入篮子里
篮子里现在糖果数 20≥n=7，因此所有小朋友获得一块糖
篮子里现在糖果数变成 13≥n=7，因此所有小朋友获得一块糖
篮子里现在糖果数变成 6<n=7，因此这 6块糖是作为你搬糖果的奖励
容易发现，你获得的作为你搬糖果的奖励的糖果数量不可能超过 6 块（不然，篮子里的糖果数量最后仍然不少于 n，需要继续每个小朋友拿一块），因此答案是 6
数据规模
| 测试点 | n≤n≤ | R≤R≤ | R−L≤R−L≤ |
|---|---|---|---|
| 1 | 2 | 5 | 5 |
| 2 | 5 | 10 | 10 |
| 3 | 10^3 | 10^3 | 10^3 |
| 4 | 10^5 | 10^5 | 10^5 |
| 5 | 10^3 | 10^9 | 0 |
| 6 | 10^3 | 10^9 | 10^3 |
| 7 | 10^5 | 10^9 | 10^5 |
| 8 | 10^9 | 10^9 | 10^9 |
| 9 | 10^9 | 10^9 | 10^9 |
| 10 | 10^9 | 10^9 | 10^9 |
2 相关知识点
1) 模运算
模运算，就是取余数，在计算机语言中用%来表示。举个简单的例子，3 % 5 = 3。结果的取值范围在 0 与模之间
例如
c=x/y
c=3 mod 5 =3 c的取值范围 [0,y-1]
结果也可以用负数表示，即 c=-2
2) 打擂台求最大值
打擂台法求最大值是一种简单直观的方法，用于在C语言中找出数组中的最大值
基本思想
初始化一个“擂主”（即假设的最大值），通常设为数组的第一个元素。
遍历数组中的其余元素，与“擂主”进行比较。
如果当前元素比“擂主”大，则将当前元素设为新的“擂主”。
遍历结束后，“擂主”即为数组中的最大值。
这种方法易于理解和实现，且效率较高，时间复杂度为O(n)，其中n为数组的长度
示例程序
#include <stdio.h>
/*
arr[] 在arr 求数组最大值 数组arr长度为n
a[0] 作为最开始擂主
*/
int findMax(int arr[], int n) {
int max = arr[0]; // 初始化擂主为数组的第一个元素
for (int i = 1; i < n; i++) { // 从数组的第二个元素开始遍历
if (arr[i] > max) { // 如果当前元素比擂主大
max = arr[i]; // 更新擂主为当前元素
}
}
return max; // 返回最大值
}
int main() {
int arr[] = {3, 5, 1, 8, 2};
int n = sizeof(arr) / sizeof(arr[0]); // 计算数组长度
int maxValue = findMax(arr, n);
printf("数组中的最大值为：%d\n", maxValue);
return 0;
}
/*
输出
数组中的最大值为：8
*/
3 思路分析
思路1
如果糖果比n大就分给其他小朋友，其实自己只能留下不能被分的余数个糖果
从L~R求出每个数的余数，然后求余数的最大值
示例程序
#include<bits/stdc++.h>
using namespace std;
/*
maxN 求最大，赋值一个最小数
n个小朋友
L最少L个糖果
R最多R个糖果
cur 枚举时临时变量，比较使用
*/
int maxN=-1,n,L,R,cur;
/*
L~R之间的数字逐一取模取最大
*/
int main(){
cin>>n>>L>>R;//输入n个小朋友 L糖果的下界 R糖果的上界
for(int i=L;i<=R;i++){//从下届枚举到上界
cur=i%n;//取模
if(cur>maxN){//找出所有取模后的最大值
maxN=cur;
}
}
cout<<maxN;
return 0;
}
由于本题测试数据比较大，可以达到10^9,打擂台求最大值的时间复杂度为O(n),会超时，具体如下
思路2
如果糖果比n大就分给其他小朋友，其实自己只能留下不能被分的余数个糖果
分析余数可知，L~R的范围有1种情况
L~R的范围，在n范围内，即 R-L<n
此时余数最大为R%n，剩余糖果的数量为R%n
L~R的范围，大于n，R-L>n
次数余数最大为余数的最大值n-1，剩余糖果的数量为n-1
#include<bits/stdc++.h>
using namespace std;
/*
分情况讨论
如果在同周期，取上界和人数取模
例如 n=6 L=7 R=11 ,则分糖果最大数11%6=5
如果在不同周期,为总人数-1
例如 n=6 L=10 R=13，则分糖果最大数6-1=5 对应11%6=5
*/
int n,L,R;//n个小朋友 L最少L个糖果 R最多R个糖果
int main(){
cin>>n>>L>>R;//输入n个小朋友 L糖果的下界 R糖果的上界
if(L/n==R/n){//如果在同周期
cout<<R%n;//取上界和人数取模
}else{//如果跨周期
cout<<n-1;//为总人数-1
}
return 0;
}
时间复杂度为模运算，O(1)
原文地址：https://blog.csdn.net/ya888g/article/details/142714427
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！