Computer programming is an art, because it applies accumulated knowledge to the world, because it requires skill and ingenuity, and especially because it produces objects of beauty. A programmer who subconsciously views himself as an artist will enjoy what he does and will do it better.
–- Donald Knuth
本教材由成大電腦網路愛好社社員以及成大競技程式設計課程助教共同編輯,雖然市面上已經有很多很棒的演算法的教材及參考書,但我們的目標在於寫出平易近人的競賽程式設計入門書及參考資料,同時加深我們自己對各種演算法的理解。
本著作採用創用 CC 姓名標示-相同方式分享 3.0 台灣 授權條款授權,
任何人都可以自由使用及分享我們的文字
教材中若沒特別說明則將 作為初始輸入規模的大小。
教材中若無特別聲明,則所有圖像或程式碼都屬於 Public Domain
句子/名詞加上粗體代表它很重要
句子/名詞加上斜體則代表這邊稍微思考一下
在每節主題後將給予一些範例以及練習,
所謂"範例"就是給道題目,並且會附上該解法;"練習"則是讀者自己該去解的題目。
演算法是解決問題的一個具體步驟,通常分成[1]:
舉例來說,
今天你不小心打翻了可樂,你想要擦乾它,現在你考慮:
你需要節省資源,所以衛生紙要用得最少
我們要考慮的因素就要有,一張衛生紙能吸多少可樂,
並且要有效率一點,我們可以算出它吸可樂的花費時間。
我們能將這個演算法分為:
這三個步驟相當重要,
在分析別人的演算法又或是自己設計,最好都要想想有沒有符合。
同一件事可能有許多解決方案,這時候我們透過各種方式評估哪種演算法較適當,以提高效率。
切記,各演算法沒有絕對的優劣,根據不同的場合給予適當的實作才是根本之道
演算法競賽是種透過寫出演算法來比較的比賽。
競賽通常會有數個題目,參賽者需要寫出或設計適當的演算法和資料結構以在規範的時間、空間解決問題。
因此,參賽者需要對各種資料結構和演算法有深入瞭解才能建構出合理的解題思路,也是算法競賽具體在比較的地方。
比賽分為實體賽與線上賽,提交程式碼並給予評判的系統稱為 Online Judge (簡稱 OJ)
當然平時練習也用 OJ
將寫出來的解交到 OJ 上,就會得到某幾種可能的結果(只會顯示一種):
一個有趣的狀況是,有時候即使是 AC,也不見得你寫的解是正確的解答,是對方給的測試資料不夠嚴格。
優格可以是開胃菜,主菜或甜點的營養成分,但必須在它過期前食用,它可能會很快過期!此外,不同的優格可能在不同的日子到期。
露西喜歡優格,她剛買了 杯優格,但她擔心她可能無法在過期之前食用所有優格。第 杯優格將從今天開始起過 天過期,並且一個優格在過期當天或之後都不能食用。
儘管露西喜歡優格,但她每天只能吃至多 杯優格。從今天開始她可以吃掉的優格數量最多是多少?
輸入的第一行給出了測試資料的數量 。每個測試資料以包含兩個整數 和 的一行開始,接著 個整數
對於每筆測試資料,輸出一行包含 Case #x:y
,其中x
是測試資料編號(從 1 開始),y
是露西可以消耗的最大優格杯數,如上所述。
限制:
1 ≤ ≤ 100.
1 ≤ ≤ .
1 ≤ ≤ , for all .
小資料:
1 ≤ ≤ 1000.
= 1.
大資料:
1 ≤ ≤ 5000.
讀完題目後,咱們開始分析吧!
看看這些條件和環境,
先把題目會用上的變數寫上:
解法就寫在 main()
中吧
並且先輸入 , 每次要餵 次測試資料:
(其中以後我們約定 :
接著下行 .
, 表示這個區塊將有一些指令被省略)
而接著可能得用上一點生活經驗,
我們會想到:是不是應該優先吃保存期限低的優格?而且當然一定要一天吃上 個優格
既然有靈感了,那就該嘗試一下這樣的決策是否能讓露西吃到最多的優格
總之先輸入測試資料
接著我們得先將所有優格按保存期限排序 (要優先吃期限最小的)
如果這個優格不能吃了,理論上 要小於等於
(其中 表示從起點那天,總共過了多少天; 為某個優格的期限)
而露西吃了 個優格就該讓一天結束,那麼我們有 if(eat == K) day++;
(其中 eat
紀錄目前該天共吃了幾個優格)
綜合起來,當今天是第 天時,優格期限從小到大
如果 就得看是否 依此類推… 直到否,就能將此優格吃掉!
所以有:
我們建議,在思考解法或是理解別人的解法的時候,應該也要從結尾往回開始去看。
也就是:
上述兩段的動機是什麼?
以下是完整解題程式碼:
bits/stdc++.h
: 此標頭檔包含很多常用的標頭檔,使用 GNU GCC 的環境都有,比賽前最好先確認環境
有 隻螞蟻以每秒 cm 的速度在一根 cm 的竿子上爬,當螞蟻爬到竿子的尾端時它會掉下去,當兩隻螞蟻相遇時,他們不能交錯通過,只能各自反向爬回去。
對於每隻螞蟻我們有它與竿子左端的距離 ,但是不知道它們的朝向,要求所有螞蟻掉落的最短時間與最長時間。
input:
題目一開始給你一個數字 [2],代表總共有幾筆測試資料。
接著每筆測資有兩行,第一行有兩個數字:這根竿子的長度 ,還有共有幾隻螞蟻 ;
接著第二行給你 隻螞蟻與竿子左端的距離 。
其中
output:
對於每筆測資獨立一行,輸出兩個數字(以空白分隔):最短掉落時間與最長掉落時間。
sample input:
sample output:
各位可以稍微想一下這題要怎麼解?
底下將簡單分析一下,並給出解答:
樸素的會想到一個暴力的模擬,也就是每一隻螞蟻的狀態都要考慮(朝左,朝右),每個螞蟻可選 種狀態,總共 種選法。
但這樣實在是太沒效率了,稍微手算模擬一下就能感受得出來。
有沒有更好的方法?
如果仔細琢磨題目給的限制及目標,會發現螞蟻哪隻是哪隻並不重要,
意思是可以把螞蟻的碰撞背離視為交錯而行(題目騙我QAQ)
這樣,只需看哪隻螞蟻最慢最快掉落。
時間複雜度是線性的 [3]。