| tags |
|---|
成大高階競技程式設計 2020, ys |
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 台灣 授權條款授權， 任何人都可以自由使用及分享我們的文字
教材中若沒特別說明則將
句子/名詞加上粗體代表它很重要 句子/名詞加上斜體則代表這邊稍微思考一下
在每節主題後將給予一些範例以及練習， 所謂"範例"就是給道題目，並且會附上該解法；"練習"則是讀者自己該去解的題目。
演算法是解決問題的一個具體步驟，通常分成1:
- 初始化
- 循環保持
- 終止
舉例來說， :::info 你的目標是吃完一包大薯，每次可以吃一根薯條 要算出一包大薯有幾根薯條 :::
能將這個演算法分為：
- 初始化： {
檢查有沒有一包大薯，沒有就去買;
吃了幾根薯條 設為
$0$ ; } - 循環保持： {
每次從那一包大薯裡面拿一根薯條;
吃掉那一根薯條;
吃了幾根薯條 加上
$1$ ; 檢查終止條件，達成則跳出，否則繼續執行循環保持; } - 終止： 大薯吃完了;
這三個步驟相當重要， 在分析別人的演算法又或是自己設計，最好都要想想有沒有符合。
同一件事可能有許多解決方案，這時候我們透過各種方式評估哪種演算法較適當，以提高效率。 切記，各演算法沒有絕對的優劣，根據不同的場合給予適當的實作才是根本之道
演算法競賽是種透過寫出演算法來比較的比賽。 競賽通常會有數個題目，參賽者需要寫出或設計適當的演算法和資料結構以在規範的時間、空間解決問題。
因此，參賽者需要對各種資料結構和演算法有深入瞭解才能建構出合理的解題思路，也是算法競賽具體在比較的地方。
比賽分為實體賽與線上賽，提交程式碼並給予評判的系統稱為 Online Judge (簡稱 OJ)
當然平時練習也用 OJ
將寫出來的解交到 OJ 上，就會得到某幾種可能的結果(只會顯示一種)：
- AC (accepted)： 提交的程式產生的解答符合系統所給的所有測試資料
- WA (wrong answer)： 產生的解答不符合系統給的測試資料
- CE (compilation error)： 程式碼編譯錯誤，最好比對一下編譯器是哪家版本
- RE (runtime error)： 通常是陣列超出範圍、指標指向不該指的位置、除以 0，或是遞迴過深等等的
- TLE (time limitation exceeded）： 程式運行的時間超過系統所限制的時間
- MLE (memory limitation exceeded)： 程式記憶體使用量超過系統所限制的空間
一個有趣的狀況是，有時候即使是 AC，也不見得你寫的解是正確的解答，是對方給的測試資料不夠嚴格。
優格可以是開胃菜，主菜或甜點的營養成分，但必須在它過期前食用，它可能會很快過期！此外，不同的優格可能在不同的日子到期。
露西喜歡優格，她剛買了
輸入的第一行給出了測試資料的數量
對於每筆測試資料，輸出一行包含 Case #x：y，其中x是測試資料編號（從 1 開始），y 是露西可以消耗的最大優格杯數，如上所述。
限制：
小資料：
大資料：
Input
4
2 1
1 1
5 1
3 2 3 2 3
2 2
1 1
6 2
1 1 1 7 7 7
Output
Case #1: 1
Case #2: 3
Case #3: 2
Case #4: 5讀完題目後，咱們開始分析吧! 看看這些條件和環境， 先把題目會用上的變數寫上：
int const maxn = 5e3 + 10;
int N, K, A[maxn];解法就寫在 main() 中吧
並且先輸入
int main()
{
int T;
scanf("%d", &T);
while (T--) {
:
.
}
return 0;
}(其中以後我們約定 : 接著下行 ., 表示這個區塊將有一些指令被省略)
而接著可能得用上一點生活經驗，
我們會想到：是不是應該優先吃保存期限低的優格？而且當然一定要一天吃上
總之先輸入測試資料
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);接著我們得先將所有優格按保存期限排序 (要優先吃期限最小的)
sort(A, A+N);如果這個優格不能吃了，理論上
而露西吃了 if(eat == K) day++;
(其中 eat 紀錄目前該天共吃了幾個優格)
綜合起來，當今天是第
所以有：
int day = 0, eat = 0;
int cnt = 0; // cnt := 紀錄最後吃了多少
for (int i = 0; i < N; i++) {
if (A[i] - day <= 0) continue;
else {
eat++;
cnt++;
}
if (eat == K) {
day++;
eat = 0;
}
}我們建議，在思考解法或是理解別人的解法的時候，應該也要從結尾往回開始去看。 也就是：
- 當露西當天吃完了
$K$ 個，就讓今天過完？ - 將優格按照保存期限排序？
上述兩段的動機是什麼？
以下是完整解題程式碼：
#include<bits/stdc++.h>
using namespace std;
int const maxn = 5e3 + 10;
int N, K, A[maxn];
int main()
{
int T, kase = 0;
scanf("%d", &T);
while (T--) {
scanf("%d%d", &N, &K);
for (int i = 0; i < N; i++) scanf("%d", &A[i]);
sort(A, A+N);
int day = 0, eat = 0;
for (int i = 0; i < N; i++) {
if (A[i] - day <= 0) continue;
if (++eat % K == 0) day++;
}
printf("Case #%d: %d\n", ++kase, eat);
}
return 0;
}
bits/stdc++.h： 此標頭檔包含很多常用的標頭檔，使用 GNU GCC 的環境都有，比賽前最好先確認環境
範例 POJ 1852 Ants：
有
input:
題目一開始給你一個數字
output: 對於每筆測資獨立一行，輸出兩個數字(以空白分隔)：最短掉落時間與最長掉落時間。
sample input:
2
10 3
2 6 7
214 7
11 12 7 13 176 23 191sample output:
4 8
38 207各位可以稍微想一下這題要怎麼解？ 底下將簡單分析一下，並給出解答：
樸素的會想到一個暴力的模擬，也就是每一隻螞蟻的狀態都要考慮(朝左，朝右)，每個螞蟻可選
有沒有更好的方法？ 如果仔細琢磨題目給的限制及目標，會發現螞蟻哪隻是哪隻並不重要， 意思是可以把螞蟻的碰撞背離視為交錯而行(題目騙我QAQ) 這樣，只需看哪隻螞蟻最慢最快掉落。
#include<bits/stdc++.h>
using namespace std;
int main() {
int T;
scanf("%d", &T);
while (T--) {
int L, n;
scanf("%d%d", &L, &n);
int x, mint = 0, maxt = 0; // 最小時間和最大時間
for (int i = 0; i < n; i++) {
scanf("%d", &x);
mint = max(mint, min(L-x, x));
maxt = max(maxt, max(L-x, x));
}
printf("%d %d\n", mint, maxt);
}
return 0;
}時間複雜度是線性的