首页 > 资讯版块 > 国际竞赛 > 更多资讯

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

发布时间：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;