Algorithm's HW in C++

HW1 :  

對於二維平面空間上的兩點 Pi(xi, yi) 及 Pj(xj, yj)，定義「Pi 優於 Pj 若且唯若 xi ≥ xj 且 yi ≥ yj」
給定二維平面空間上 n 個不重複的點，其點座標為 Pi(xi, yi)，可以計算出每一點的rank
對於一點的 rank 定義為「該點優於其它點的數目」
時間複雜度為O(nlogn)
並追加計算出Optimal Threshold Value的部分  

輸入含有多筆測資  
每一筆測資第一行為 n，代表有 n 個點  
接下來有 n 行，這 n 行中的第 i 行有兩個數字，xi, yi，代表第 i 個點的座標  
當 n 為 0 時表示輸入結束  
每筆測資輸出一行，每一行包含 n 個數，這 n 個數的第 i 個數為第 i 個點的 rank

• 5 ≤ n ≤ 100000
• -2147483648 ≤ xi, yi ≤ 2147483647
• n ∈ N
• xi, yi ∈ Z

HW2 :

Given two sequences X =〈x1, x2, … , xm〉and Y = 〈y1, y2, … , yn〉, find a maximum-length common subsequence of X and Y
只需使用 O(n) 的額外空間

第一行為 t，代表共有 t 筆測資  
接下來有 t 行，每行皆有兩個字串，依序為 X 及 Y，長度分別為 m 和 n  
每筆測資輸出一行，為該筆測資之 X 與 Y 的 LCS  
若存在多種 LCS，則任意輸出一種即可  
若不存在 LCS，則輸出空行  

• 2 ≤ t ≤ 20
• 5 ≤ m, n ≤ 1,000

HW3 :

給定一個工作集 S = { s1, s2, s3 … sn }，每個工作 si 都有所需的處理時間 ti 與截止時間 di，一旦開始工作就要花費 ti 的時間完成
此程式可以計算出在截止時間內最多能完成的工作數量
方法為: 將工作依序放入最大堆積（依處理時間），每當最後放入的工作超過其截止時間則從堆積取出處理時間最久的工作，最後堆積的大小即為最多能完成的工作數量
本演算法的時間複雜度為 O(nlogn)  

輸入第一行為 k，代表共有 k 筆測資  
每筆測資第一行為 n，代表這筆測資有 n 個工作  
接下來 n 行，每行皆有兩個數字 ti 與 di，表示這個工作的處理時間及截止時間  
每筆測資輸出一行，為該筆測資最多能完成的工作數量  

• 1 ≤ k ≤ 20  
• 1 ≤ n ≤ 50,000  
• 1 ≤ ti ≤ 20,000  
• ti ≤ di ≤ 2,147,483,647  
• k, n, ti, di ∈ N

HW4 :

給一個無向、有權重的簡單連通圖，請實作一個程式，計算最小生成樹的權重總合
實作的演算法是 Kruskal’s Algorithm
時間複雜度為 O(ElogV)  

輸入含有多筆測資，最多二十筆  
每一筆測資第一行為 n 與 m，代表這筆測資有 n 個點與 m 條邊  
接下來有 m 行，其中每行皆有三個數字 x、y、w，代表第 x 個點與第 y 個點之間有邊，其權重為 w  
測資必定為簡單（Simple）連通（Connected）圖  
當 n 與 m 皆為 0 時表示輸入結束  
每筆測資輸出一行，為其最小生成樹之權重和  

• 1 ≤ n ≤ 10000  
• n - 1 ≤ m ≤ min(n * (n - 1) / 2, 100000)  
• 0 ≤ x, y ≤ n - 1  
• -20000 ≤ w ≤ 20000  
• n ∈ N  
• m, x, y ∈ Z*  
• w ∈ Z