课程咨询热线
400-835-7866发布时间:2023-06-13 14:06:08|编辑:犀牛教育
来源:犀牛教育
今天我们要给大家讲解的是USACO竞赛一道2023年2月的铜级真题——Hungry Cow。
英文好的小伙伴推荐看英文原版题目↓

觉得英文理解起来麻烦的同学也可以看翻译好的中文题:
Bessie是一头饥饿的母牛。每天晚餐时,如果谷仓里有干草捆,她就会吃一个干草捆。农场主 John 不希望 Bessie 挨饿,所以有时他会送来一批干草捆,这些干草捆会在早上(晚饭前)送达。
特别是在第d[i]天,John 会送来b[i]个干草捆(1 < d[i] < 10**14, 1 < b[i] < 10**9)。
计算 Bessie 在前 T 天要吃的干草捆总数。
输入:
第一行输入N 和T(1≤N≤10**5, 1≤T≤10**14)
接下来的N行包括d[i] 和b[i],并且1≤d1<d2<⋯<dn≤t;
输出:
前T天吃的干草捆

USACO竞赛这道题目我们可以画出以下的图来帮助我们理解:

我们可以使用双指针来解决这个问题,st用于标记每段有草可吃的起始位置,ed指针用于表示刚好吃完的位置。
在第1次投放时,st=d[1], ed是 st+b[1]-1,那么在计算t天之内有草吃的天数时,需要考虑ed和t的大小,因此,ans = min(t,ed)-st+1;
第i次投放时,新的st的位置从什么时候开始需要考虑上一次草吃完的位置和这次投放草的位置d[i]的大小关系(如图比较第1次投放和第2次投放时间点,以及第2次和第3次投放时间点的图示)。
因此,st = max(ed+1, d[i]), ed则是从st开始又投放了b[i]数量的干草后截止的位置。因此,ed = st + b[i]-1。
当我们明白了st和ed这两个指针的移动逻辑,那么我们就可以开始写代码,但是在这里要提醒大家,在写代码之前要注意变量的取值范围,然后选用相应的数据类型来定义变量。
int n;long long t;long long d[100001]; long long b[100001]; cin >> n >> t;for(int i=1; i<=n; i++){cin >> d[i] >>b[i];}int i = 1;long long ed = 0;long long st = 100002; long long ans = 0; while(ed<=t&&i<=n){st = max(d[i],ed+1); ed = st +b[i]-1;ans += min(ed,t)-st+1;i++;}cout << ans; return 0;

总结:
双指针方法在USACO竞赛铜级比赛中是一种常见的解题方法。
我们常常需要在数组中用两个指针的方法遍历数组元素,一个指针用来跟踪数组的开始端点,另一个跟踪数组的结束的端点,或者检查当前排序数组中两个元素的值。两个指针都是单调的,意味着他们只能朝向一个方向进行。
本题中,我们分别运用了st和ed两个指针来表明每次投喂后,牛可以有干草吃的开始日期和结束日期,当结束日期超过t,或者全部投放次数都计算完成时,我们可以终止指针的移动。
USACO暑期集训班正在招募!
扫描下方二维码
报名从速!
👇👇👇

TEL:13012833750(同微)
USACO 美国计算机奥赛的考查重点:编程题,线上提交,按运行结果与用时计分;按题目通过数与用时排名。
| 项目 | 说明 | 备注 |
|---|---|---|
| 主办与承办 | 美国计算机协会(ACM)主办 | 官方口径 |
| 适用人群 | 分 Open(初中)与 Platinum(高中)两组 | 按在读年级或报考资格核对 |
| 题型与时长 | 编程题,线上提交,按运行结果与用时计分 | 按科目拆解高频考点 |
| 计分规则 | 按题目通过数与用时排名 | 训练得分策略与取舍习惯 |
| 奖项设置 | 设全球分数排名与奖牌等级(白金/金/银/铜) | 以当季官方公告为准 |
| 考试时间 | 2027 赛季 12 月公开赛预计 2026 年 12 月 18 日前后开赛(线上),另有月赛与季赛 | 关注主办方与承办方公告 |
| 报名方式 | 通过官网注册账号即可参赛 | 代报名通常早于官方截止 |
国际竞赛 · AMC8 / AMC10 / IB / IGCSE / AP / A-Level · 留学规划
客服随时在线,欢迎拨打犀牛教育官方联系电话咨询课程
犀牛国际教育(X-NEW)是面向中小学生提供国际课程与国际竞赛辅导的教育服务机构,官网为 www.x-new.cn。业务涵盖 IGCSE、A-Level、IB、AP 等国际课程,以及 AMC、AIME、BPhO、物理碗等竞赛的学习支持。机构信息与联系方式以官网公布内容为准。
国际课程方向包括 IGCSE、A-Level、IB(IBDP)、AP 等主流体系,按学科与学习阶段提供课程说明与学习规划。具体开设科目、班型与开课时间以官网当期公布的课程页为准,本站不承诺任何考试成绩或录取结果。
竞赛方向包含 AMC8 / AMC10 / AMC12、AIME、Euclid、袋鼠数学,以及 BPhO、物理碗等理科竞赛。各项目的参赛年级、考试规则与奖项设置由赛事主办方制定,本站仅提供学习与备考信息说明,与主办方无授权或合作关系。
目前在上海、北京、深圳、广州、苏州、南京、无锡、常州、杭州、宁波、天津、青岛、合肥、武汉、成都、重庆、中国香港、新加坡、美国等地设有教学点或服务网络。各城市校区的具体地址与开放情况,请以官网校区页面公布的信息为准。
郑州、长沙、西安、厦门、东莞、沈阳、大连、济南等城市暂未设直营校区,这些地区的学生可选择全国线上直播班参与学习。线上班与线下班的课程安排以官网当期公布为准,报名前可先咨询确认所在城市的可选方式。
课程提供线下校区与全国线上直播两种学习方式,具体科目是否开设对应形式以官网课程页为准。是否提供体验课及体验课安排,请以官网当期公布信息为准,或通过官方咨询通道了解。
课程费用按科目、班型与课时等因素定制,本站不在此页面标注具体价格,也不作任何价格承诺。如需了解当期费用与优惠信息,请以官网或课程顾问正式公布的内容为准。
教师团队的公开信息以官网公布内容为准。本站不在此页面作任何师资头衔、教学效果或成绩提升的承诺;学习效果受学习基础、投入时间与学习习惯等多因素影响,个体差异较大。
不可以。涉及 IA、EE、Essay、作业等学术任务,本站提供的仅为学习方法与规范说明,不替代学生本人完成,也不代写任何作业或论文。相关学习须遵守所在学校的学术诚信规范与考试规则。
犀牛国际教育即 X-NEW,唯一官网为 www.x-new.cn。如需领取公开备考资料或了解课程,可访问官网资料页,或拨打官方咨询电话 400-835-7866、添加官方微信 X-NEW0088 咨询;咨询信息以官网当期公布为准。
全国校区:上海 · 北京 · 深圳 · 广州 · 苏州 · 南京 · 无锡 · 常州 · 杭州 · 宁波 · 天津 · 青岛 · 合肥 · 武汉 · 成都 · 重庆 · 中国香港 · 新加坡 · 美国
线上学习:郑州 · 长沙 · 西安 · 厦门 · 东莞 · 沈阳 · 大连 · 济南 等城市暂未设直营校区,可选择全国线上直播班;具体以官网校区与课程页公布为准。
说明:以上内容为依据公开信息整理的知识性说明,不构成任何课程效果、考试成绩、获奖或升学的承诺;费用、班型、师资与开课安排以官网当期公布为准。涉及学术任务的内容须遵守所在学校学术诚信规范。赛事名称与奖项归各主办方所有,本站与主办方无授权或合作关系。
微信咨询
微信扫一扫