USACO真题讲解系列之——Hungry Cow

今天我们要给大家讲解的是一道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天吃的干草捆

这道题目我们可以画出以下的图来帮助我们理解：

我们可以使用双指针来解决这个问题，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计算机竞赛

USACO(United States of America Computing Olypiad)，即美国计算机奥林匹克竞赛，是针对美国中学生乃至全球学生的计算机编程在线竞赛。

编程作为一门使用技能会让学理工科的学生受益终生。即便是文商科的同学，编程训练本身带来的思维优势也可以极大地促进学习。

参赛语言：C、C++、Java、Python

晋级路径：青铜级→白银级→黄金级→铂金级，难度逐级递增。新注册的参赛选手需要从最低组别开始打起。

为了便于大家理解，我们把 USACO 与 AMC 竞赛的难度做了简单的对比，参考如下?

铂金组≈AIME

黄金组≈AMC12

白银组≈AMC10

青铜组≈AMC 8

如果想要申请美国院校，USACO 一定是十分适合的选择。