筆試算法模拟題精解之“采摘聖誕果”

【線上程式設計産品介紹】

阿裡雲開發者社群線上程式設計：

免費刷題大神器，助你拿到好offer

周賽月賽不停歇，做題還能領獎品

大賽筆試全真題，常做常新有驚喜

點選連結開始産品體驗：

https://developer.aliyun.com/coding 本文為大家介紹的是“101.采摘聖誕果”的解法探究。先來看一下題目内容：

題目詳情

等級：中等

知識點：貪心

檢視題目：采摘聖誕果

聖誕節馬上就要來了，果園裡的 n 棵聖誕樹馬上就要結果子了，每棵聖誕樹會在第a[i]天結出b[i]個果實。果園裡有許多聖誕小精靈，它們非常喜歡吃聖誕果，如果在結果後兩天内也就是第a[i]天和第a[i]+1天，沒有将果實采摘下來，那麼将會被小精靈們偷吃掉。

你，作為聖誕樹的看守者，必須采摘盡可能多的聖誕果，但是你每天最多隻能采摘v個聖誕果，當然，可以是不同的果樹上的。現在你需要判斷自己最多可以收獲多少聖誕果。

輸入聖誕樹棵樹n、每天最多采摘的聖誕果數量v和一個數組m，其中m[i]=[a[i], b[i]]表示每棵聖誕樹第a[i]天結出b[i]個果實（1 <= n，a[i]，b[i] <= 3000）。

輸出一個數字，表示最多可以收獲的聖誕果數。

示例1

輸入：

3

[[1,3],[2,5],[3,4]]

輸出：

12

注意

你可以在第一天在第一棵樹上摘三個，第二天在第二棵樹上摘三個，第三天在第二棵樹上摘兩個，然後再在第三顆樹上摘一個，第四天在第三棵樹上摘三個。

解題思路描述

我們定義數組a[i]表示第i天可以采摘的剛剛結出來的果子，數組b[i]表示第i天可以采摘的已經過了一天的果子。根據輸入先初始化a[]。

假設我們目前處于第i天，那麼顯然我們應該采摘b[i]中的果實，然後再采摘a[i]中的果實，因為如果不采摘b[i]中的果實，則它們會在下一天被偷吃。在更新之後a[i]中剩餘的果實會在下一天變成b[i]中的果實。

時間複雜度：O(3000)

空間複雜度：O(3000)

看完之後是不是有了答題思路了呢，快來練練手吧：

101.采摘聖誕果

線上程式設計周賽、月賽火熱進行中，更有限時答題活動，社群定制衛衣、雙肩背包等你來拿~每天都有好禮相送~點選了解周賽詳情：

線上程式設計3月份比賽正式開啟！機械鍵盤等你拿！