|
今天我们要给大家讲解的是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（同微） |
