USACO真題講解係列之——Hungry Cow

今天我們(men) 要給大家講解的是一道2023年2月的銅級真題——Hungry Cow。

英文好的小夥(huo) 伴推薦看英文原版題目↓

覺得英文理解起來麻煩的同學也可以看翻譯好的中文題：

Bessie是一頭饑餓的母牛。每天晚餐時，如果穀倉(cang) 裏有幹草捆，她就會(hui) 吃一個(ge) 幹草捆。農(nong) 場主 John 不希望 Bessie 挨餓，所以有時他會(hui) 送來一批幹草捆，這些幹草捆會(hui) 在早上（晚飯前）送達。

特別是在第d[i]天，John 會(hui) 送來b[i]個(ge) 幹草捆（1 < d[i] < 1014, 1 < b[i] < 109)。

計算 Bessie 在前 T 天要吃的幹草捆總數。

輸入：

第一行輸入N 和T（1≤N≤105, 1≤T≤1014）

接下來的N行包括d[i] 和b[i]，並且1≤d1<d2<⋯<dn≤t；

輸出：

前T天吃的幹草捆

這道題目我們(men) 可以畫出以下的圖來幫助我們(men) 理解：

我們(men) 可以使用雙指針來解決(jue) 這個(ge) 問題，st用於(yu) 標記每段有草可吃的起始位置，ed指針用於(yu) 表示剛好吃完的位置。

在第1次投放時，st=d[1], ed是 st+b[1]-1，那麽(me) 在計算t天之內(nei) 有草吃的天數時，需要考慮ed和t的大小，因此，ans = min(t,ed)-st+1;

第i次投放時，新的st的位置從(cong) 什麽(me) 時候開始需要考慮上一次草吃完的位置和這次投放草的位置d[i]的大小關(guan) 係（如圖比較第1次投放和第2次投放時間點，以及第2次和第3次投放時間點的圖示）。

因此，st = max(ed+1, d[i]), ed則是從(cong) st開始又投放了b[i]數量的幹草後截止的位置。因此，ed = st + b[i]-1。

當我們(men) 明白了st和ed這兩(liang) 個(ge) 指針的移動邏輯，那麽(me) 我們(men) 就可以開始寫(xie) 代碼，但是在這裏要提醒大家，在寫(xie) 代碼之前要注意變量的取值範圍，然後選用相應的數據類型來定義(yi) 變量。

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競賽銅級比賽中是一種常見的解題方法。

我們(men) 常常需要在數組中用兩(liang) 個(ge) 指針的方法遍曆數組元素，一個(ge) 指針用來跟蹤數組的開始端點，另一個(ge) 跟蹤數組的結束的端點，或者檢查當前排序數組中兩(liang) 個(ge) 元素的值。兩(liang) 個(ge) 指針都是單調的，意味著他們(men) 隻能朝向一個(ge) 方向進行。

本題中，我們(men) 分別運用了st和ed兩(liang) 個(ge) 指針來表明每次投喂後，牛可以有幹草吃的開始日期和結束日期，當結束日期超過t，或者全部投放次數都計算完成時，我們(men) 可以終止指針的移動。

USACO計算機競賽

USACO(United States of America Computing Olypiad)，即美國計算機奧林匹克競賽，是針對美國中學生乃至全球學生的計算機編程在線競賽。

編程作為(wei) 一門使用技能會(hui) 讓學理工科的學生受益終生。即便是文商科的同學，編程訓練本身帶來的思維優(you) 勢也可以極大地促進學習(xi) 。

參賽語言：C、C++、Java、Python

晉級路徑：青銅級→白銀級→黃金級→鉑金級，難度逐級遞增。新注冊(ce) 的參賽選手需要從(cong) 最低組別開始打起。

為(wei) 了便於(yu) 大家理解，我們(men) 把 USACO 與(yu) AMC 競賽的難度做了簡單的對比，參考如下?

鉑金組≈AIME

黃金組≈AMC12

白銀組≈AMC10

青銅組≈AMC 8

如果想要申請美國院校，USACO 一定是十分適合的選擇。