课程咨询热线
400-835-7866
课程咨询热线
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 · 留学规划
客服随时在线，欢迎拨打悠米下载安装官方联系电话咨询课程
联系我们
400-835-7866
版权所有：悠米下载安装 备案号 沪ICP备2024045959号-4沪公网安备31010402333891号
微信咨询
微信扫一扫