算法專題（1）-資訊學基本解題流程！
【文章來源：清北學堂微信訂閱号noipnoi】
摘要
本次系列文章主要介紹資訊學以下知識點
今天我們主要看資訊學基本解題流程：
一、 基本解題流程
1.概述：
資訊學中解算法題跟數學中解應用題十分類似，大緻分為以下四個步驟：題意了解與模型建立、算法設計與複雜度分析、代碼編寫、調試。
2. 知識點梳理：
Ø 題意了解與模型建立
題意了解是算法設計的第一步，也是非常關鍵的一步。與做數學應用題一樣，需要将原題抽象成相對應的數學或邏輯形式，再參考不同的模型進行模組化。常見的模型有搜尋模型、組合數學模型、動态規劃模型、樹圖模型等。
Ø 算法設計與複雜度分析
設計算法與分析複雜度是整個解題過程中最重要的部分。設計算法時，需要考慮算法的正确性，尤其是對于貪心類型的題目求解時。分析複雜度可以大緻确認算法能跑多快，在比賽中可以過多少個資料點。
通常來講，計算機在一秒内的運算次數大緻是107（千萬）到108（億）的量級，如果把n代入複雜度的表達式，得數大于107，就會有逾時的可能。
Ø 代碼編寫
寫代碼之前，在紙上寫一下僞代碼，既可以幫助整理思路，也可以加快代碼編寫的速度。在代碼的編寫過程中，變量命名規則，循環中左右括号的分布（左括号是否換号），縮進等需要有一個固定的格式。這樣不僅可以使得代碼更加美觀，也可在後續調試中減少不必要的麻煩。關鍵代碼部分應适當加些注釋，友善自己調試。
Ø 代碼調試
在代碼編寫完成後，不能保證其完全正确，這時候，需要對其進行調試。調試過程大緻分為以下幾點：
靜态查錯：不要運作程式。靜下心來，慢慢地用你的思路、框圖和僞代碼檢查代碼，看是否有打錯的或者漏打的内容。一般要先查局部，後查整體。（調試前先靜态查錯，如果忽略，很容易因為長時間找不到錯誤而造成緊張、焦慮的情緒，進而影響答題。）
黑箱測試：測試示例。如果示例的結果都不對，就應該考慮算法的正确性，并檢查代碼是否寫錯。
構造小資料：根據程式功能設計幾個資料，檢查程式是否計算出正确結果。
構造極端資料：在時間允許的情況下，按照題目中的資料要求，嘗試構造極端資料，測試自己的程式。
輸出中間結果：有時候程式的結果不正确，但通過直接觀察代碼無法找到問題，可在代碼中的關鍵部分輸出中間結果，以檢視代碼中哪部分有錯。注意：在送出之前，需要将這些用于調試的輸出注釋掉。
單步調試：有些情況下，在輸出中間結果調試時仍然找不到問題，可以進行單步調試。要注意耐心。
3. 重難點分析：
· 題意必須了解透徹，模型需要建立正确。
· 算法設計時，需要把握其正确性（尤其是貪心算法）和可行性（算法複雜度）。
· 僞代碼很重要，代碼中适當的注釋也是必要的。代碼編寫時需注意細節。
· 代碼調試時，應先靜态後動态，先整體後局部。
·
4. 例題解析：
例題1-1：數字三角形
【問題描述】有一個層數為n (n≤1000) 的數字三角形（如下圖）。現有一隻螞蟻從頂層開始向下走，每走下一級時，可向左下方向或右下方向走。求走到底層後它所經過數 字的總和的最大值。
| 1 6 3 8 2 6 2 1 6 5 3 2 4 7 6 | 最大值＝1＋3＋6＋6＋7＝23 |
|---|
【分析】本題題目描述比較清晰，可按照題目意思直接了解題意，也可構模組化型。模型建構後，本題可抽象為一個圖，圖中共有n層頂點（n≤1000），每個頂點有一個權重，第i層的頂點有i個，其中第i層中第k的頂點與i+1層中第k和k+1個頂點有路徑。需要求解的是，從第1層走到第第n層的路徑中，經過頂點權重和最大的路徑的權重和。
題意了解後，接下來就是要設計算法。本例題中，一個樸素的算法是直接模拟。先從(1,1)點開始，每次向下左下或者右下走，記錄路徑上的數字和，當走到第n層的時候結束，記錄可行解。繼續模拟，直到所有可能情況都被計算過。記錄最大的數字和，算法結束。
上述算法簡單易懂，但是實作起來複雜度很高。對于i層第k個節點(i,k)，可以向左下走到(i+1,k)或向右下走到(i+1,k+1)，每個節點上都有兩種可行方案，每一次模拟需要走n個節點。那麼需要模拟的次數是2(n-1)，也就是說，時間複雜度是O(2(n-1))。這種複雜度下，顯然不能在限定時間内出解。
當一開始設計的算法複雜度無法滿足要求時，需要考慮更有效的算法。本例中，因為隻要求解可行路徑上的最大頂點和，那麼對于節點(i,k)隻要儲存走到這個節點時，已走路徑的最大頂點和，記作f(i,k)。由于螞蟻隻能往下走，不會再回頭。對于節點(i,k)，它的最大值隻可能從節點(i-1,k-1)或節點(i-1,k)中更新，即
最後隻要求解第n層中f的最大值即可。由于每個節點隻會被更新一次，時間複雜度變為O(n*(n+1)/2)，即O(n2)。該方法運用的是動态規劃的思路，在之後動态規劃的章節會具體講述。
例題1-2：作業排程方案（NOIP2006）
【問題描述】我們現在要利用m台機器加工n個工件，每個工件都有m道工序，每道工序都在不同的指定的機器上完成。每個工件的每道工序都有指定的加工時間。
每個工件的每個工序稱為一個操作，我們用記号j-k表示一個操作，其中j為1到n中的某個數字，為工件号；k為1到m中的某個數字，為工序号，例如2-4表示第2個工件第4道工序的這個操作。在本題中，我們還給定對于各操作的一個安排順序。
例如，當n=3，m=2時，“1-1，1-2，2-1，3-1，3-2，2-2”就是一個給定的安排順序，即先安排第1個工件的第1個工序，再安排第1個工件的第2個工序，然後再安排第2個工件的第1個工序，等等。
一方面，每個操作的安排都要滿足以下的兩個限制條件。
(1) 對同一個工件，每道工序必須在它前面的工序完成後才能開始；
(2) 同一時刻每一台機器至多隻能加工一個工件。
另一方面，在安排後面的操作時，不能改動前面已安排的操作的工作狀态。
由于同一工件都是按工序的順序安排的，是以，隻按原順序給出工件号，仍可得到同樣的安排順序，于是，在輸入資料中，我們将這個安排順序簡寫為“1 1 2 3 3 2”。
還要注意，“安排順序”隻要求按照給定的順序安排每個操作。不一定是各機器上的實際操作順序。在具體實施時，有可能排在後面的某個操作比前面的某個操作先完成。
例如，取n=3,m=2，已知資料如下：
| 工件号 | 機器号/加工時間 | |
|---|---|---|
| 工序1 | 工序2 | |
| 1 | 1/3 | 2/2 |
| 2 | 1/2 | 2/5 |
| 3 | 2/2 | 1/4 |
則對于安排順序“1 1 2 3 3 2”，下圖中的兩個實施方案都是正确的。但所需要的總時間分别是10與12。
當一個操作插入到某台機器的某個空檔時（機器上最後的尚未安排操作的部分也可以看作一個空檔），可以靠前插入，也可以靠後或居中插入。為了使問題簡單一些，我們約定：在保證限制條件（1）（2）的條件下，盡量靠前插入。并且，我們還約定，如果有多個空檔可以插入，就在保證限制條件（1）（2）的條件下，插入到最前面的一個空檔。于是，在這些約定下，上例中的方案一是正确的，而方案二是不正确的。
顯然，在這些約定下，對于給定的安排順序，符合該安排順序的實施方案是唯一的，請你計算出該方案完成全部任務所需的總時間。
【輸入】
第一行為兩個數：m n（其中m<20表示機器數，n<20表示工件數）
第2行：2n個用空格隔開的數，為給定的安排順序。
接下來的2n行，每行都是用空格隔開的m個正整數，每個數不超過20。
其中前n行依次表示每個工件的每個工序所使用的機器号，第1個數為第1個工序的機器号，第2個數為第2個工序機器号，等等。後n行依次表示每個工件的每個工序的加工時間。可以保證，以上各資料都是正确的，不必檢驗。
【輸出】
輸出隻有一個正整數，為最少的加工時間。
【樣例輸入】
2 3
1 1 2 3 3 2
1 2
1 2
2 1
3 2
2 5
2 4
【樣例輸出】
10
【分析】本題題目冗長，需耐心讀題，了解題意。本題中最重要的内容是兩個限制與兩個約定。
限制：
· 對同一個工件，每道工序必須在它前面的工序完成後才能開始；
· 同一時刻每一台機器至多隻能加工一個工件。
約定：
· 保證限制條件（1）（2）的條件下，盡量靠前插入
· 如果有多個空檔可以插入，就在保證限制條件（1）（2）的條件下，插入到最前面的一個空檔。
了解了這些限制與約定，本題就是一個簡單的模拟題。按照題目所給的安排順序進行模拟，對于順序中的每一個工件，根據限制與約定，插入到機器中。