# APCS實作題2025年1月第3題：重組問題 > 日期：2025年1月14日 > 作者：王一哲 > [ZeroJudge 題目連結](https://zerojudge.tw/ShowProblem?problemid=q183) ## 題目 ### 問題描述 對於一個長度為 $n$ 的陣列 $a_1, a_2, \dots, a_n$，已知 $a_1$ 為 $0$，定義 $\Delta$ 為陣列中任兩個數字的絕對值差所組成的一群數字。給定 $\Delta$ 的內容，輸出可以生成該 $\Delta$ 的最小與最大字典序陣列。 舉例來說，如果 $n = 3$ 且 $\Delta = (3, 4, 7)$，距離最大的是 $7$，因為最大距離必定是在最小與最大兩數之間，我們可以推論原序列的最大的數字是 $7$。接著，目前已知原序列有 $(0, 7)$，而距離序列扣除 $7$ 之後剩下 $(3, 4)$，我們要決定中間點的位置。此時最大的距離是 $4$，這個距離必然是該未知點與「最小的0」或者與「最大的7」之間的距離，所以這個點可能是 $4$ 或者 $3$，在檢驗距離序列後，發現兩者皆可能，所以原序列可能是 $(0, 3, 7)$ 或者 $(0, 4, 7)$，其中字典序最小的是 $(0, 3, 7)$，最大的是 $(0, 4, 7)$。 <br /> ### 輸入說明 第一行輸入一個正整數 $n~(1 \leq n \leq 25)$，接下來一行有 $\frac{n(n-1)}{2}$ 個正整數。 子題配分 - 30%：$n \leq 6$ - 70%：無限制 <br /> ### 輸出格式 第一行輸出能生成出該 $\Delta$ 的最小字典序的陣列，第二行輸出能生成出該 $\Delta$ 的最大字典序的陣列。 <br /> ### 範例輸入1 ``` 3 3 4 7 ``` ### 範例輸出1 ``` 0 3 7 0 4 7 ``` ### 範例輸入2 ``` 5 1 2 3 3 5 5 6 8 10 11 ``` ### 範例輸出2 ``` 0 1 3 6 11 0 5 8 10 11 ``` <br /><br /> ## Python 程式碼 基本上就是看[吳邦一教授的寫法](https://hackmd.io/@bangyewu/rJlvXNP81g#%E7%AC%AC%E5%9B%9B%E9%A1%8C-%E5%88%86%E7%B5%84%E9%96%8B%E6%9C%83-ZeroJudge-q184)再加上一些自己的註解，沒什麼原創性，就不設定成公開發佈了。 費時最久約為 0.1 s，使用記憶體最多約為 3.4 MB，通過測試。 ```python= n = int(input()) # 陣列共有 n 個數字，所有的數字都在 1 ~ 100 之間 diff = sorted(list(map(int, input().split()))) # 讀取陣列中任意兩個數的差值，由小到大排序 if n == 1: # 特例 print(0); print(0) # 印出兩個 0 exit(0) # 沒有錯誤訊息，離開程式 imax = [0]*n # 最大字典序的答案，預設為小於題目範圍的 n 個 0 imin = [1000]*n # 最小字典序的答案，預設為於題目範圍的 n 個 1000 last = diff[-1] # diff 之中最後一項，最大的差值 # 自訂函式 dfs，代入已經找到的數字串列 ps, 已知的差值串列 ds，這次要測試的數字 t def dfs(ps, ds, t): global imax, imin # 全域變數，這樣才能修改 imax 及 imin 的值 for p in ps: # 依序從 ps 之中讀取數字 p target = abs(t-p) # 要找的目標差值 if target not in ds: return # 如果 target 不在 ds 之中，跳出 dfs ds.remove(target) # 已找到 target，從 ds 之中移除 target # t 是符合要求的數字 ps.append(t) # 將 t 加入 ps if not ds: # 如果 ds 是空的，已經沒有要找的數字，結束 dfs ps.sort() # 將 ps 由小到大排序 imin = min(imin, ps) # 更新 imin imax = max(imax, ps) # 更新 imax return # 結束 dfs # 遞迴 t = ds[-1] # t 改成目前 ds 中最後一項 dfs(ps.copy(), ds.copy(), t) # 要用 ps[:] 或 ps.copy() 複製資料，才不會改到原來的串列 dfs(ps.copy(), ds.copy(), last-t) # last-t 是另一組解 return # 結束 dfs # end of dfs dfs([0], diff, last) # 呼叫 dfs 求解 print(*imin) # 印出答案 print(*imax) ``` <br /> 只找最小字典序的解，再將它反過來就是最大字典序的解。費時最久約為 26 ms，使用記憶體最多約為 3.4 MB，通過測試。 ```python= n = int(input()) # 陣列共有 n 個數字，所有的數字都在 1 ~ 100 之間 diff = sorted(list(map(int, input().split()))) # 讀取陣列中任意兩個數的差值，由小到大排序 if n == 1: # 特例 print(0); print(0) # 印出兩個 0 exit(0) # 沒有錯誤訊息，離開程式 imin = [1000]*n # 最小字典序的答案，預設為於題目範圍的 n 個 1000 last = diff[-1] # diff 之中最後一項，最大的差值 # 自訂函式 dfs，代入已經找到的數字串列 ps, 已知的差值串列 ds，這次要測試的數字 t def dfs(ps, ds, t): global imin # 全域變數，這樣才能修改 imin 的值 for p in ps: # 依序從 ps 之中讀取數字 p target = abs(t-p) # 要找的目標差值 if target not in ds: return False # 如果 target 不在 ds 之中，回傳 False 跳出 dfs ds.remove(target) # 已找到 target，從 ds 之中移除 target # t 是符合要求的數字 ps.append(t) # 將 t 加入 ps if not ds: # 如果 ds 是空的，已經沒有要找的數字，結束 dfs ps.sort() # 將 ps 由小到大排序 imin = ps # 更新 imin return True # 回傳 True 結束 dfs # 遞迴，要用 ps[:] 或 ps.copy() 複製資料，才不會改到原來的串列 t = ds[-1] # t 改成目前 ds 中最後一項 if dfs(ps.copy(), ds.copy(), last-t): # last-t 是另一組解 return True # 回傳 True 結束 dfs else: return dfs(ps.copy(), ds.copy(), t) # end of dfs dfs([0], diff, last) # 呼叫 dfs 求解 print(*imin) # 印出答案 for i in range(n-1, -1, -1): # 印出 imax print(last-imin[i], end="\n" if i == 0 else " ") ``` <br /><br /> ## C++ 程式碼 費時最久約為 19 ms，使用記憶體最多約為 368 kB，通過測試。 ```cpp= #include <iostream> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; vector<int> imin (100), imax (100); // 最小、最大字典序的答案 int last; // 陣列中任意兩個數的差值之中最大的值 /* 自訂函式 dfs，代入已經找到的數字串列 ps, 已知的差值串列 ds，這次要測試的數字 t */ void dfs(vector<int> ps, vector<int> ds, int t) { // 不能改變傳入的陣列值，用傳值呼叫 for(int p : ps) { // 依序從 ps 之中讀取數字 p int target = abs(t - p); // 要找的目標差值 auto it = find(ds.begin(), ds.end(), target); // 在 ds 之中找 target if (it == ds.end()) return; // 如果 target 不在 ds 之中，跳出 dfs ds.erase(it); // 已找到 target，從 ds 之中移除 target } ps.push_back(t); // t 是符合要求的數字，將 t 加入 ps if (ds.empty()) { // 如果 ds 是空的，已經沒有要找的數字，結束 dfs sort(ps.begin(), ps.end()); // 將 ps 由小到大排序 if (ps < imin) imin = ps; // 更新 imin if (ps > imax) imax = ps; // 更新 imax return; } t = ds.back(); // t 改成目前 ds 中最後一項 dfs(ps, ds, last-t); // 遞迴，last-t 是另一組解 dfs(ps, ds, t); // 遞迴，t 是另一組解 return; } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; // 陣列共有 n 個數字，所有的數字都在 1 ~ 100 之間 if (n == 1) { // 特例 cout << "0\n0\n"; // 印出兩個 0 return 0; // 離開程式 } int m = n*(n-1)/2; // 差值數量 vector<int> diff (m); // 陣列中任意兩個數的差值 for(int i=0; i<m; i++) cin >> diff[i]; sort(diff.begin(), diff.end()); // 由小到大排序 imin.resize(n); imax.resize(n); // 調整 imin 及 imax 的大小 fill(imin.begin(), imin.end(), 1000); // 預設為於題目範圍的 n 個 1000 fill(imax.begin(), imax.end(), 0); // 預設為小於題目範圍的 n 個 0 vector<int> points = {0}; // 答案中一定有 0 last = diff.back(); // diff 之中最後一項，最大的差值 dfs(points, diff, last); // 呼叫 dfs 求解 for(int i=0; i<n; i++) cout << imin[i] << " \n"[i == n-1]; // 印出答案 for(int i=0; i<n; i++) cout << imax[i] << " \n"[i == n-1]; return 0; } ``` <br /> 只找最小字典序的解，再將它反過來就是最大字典序的解。費時最久約為 2 ms，使用記憶體最多約為 368 kB，通過測試。 ```cpp= #include <iostream> #include <cstdlib> #include <vector> #include <algorithm> using namespace std; vector<int> imin (100); // 最小、最大字典序的答案 int last; // 陣列中任意兩個數的差值之中最大的值 /* 自訂函式 dfs，代入已經找到的數字串列 ps, 已知的差值串列 ds，這次要測試的數字 t */ bool dfs(vector<int> ps, vector<int> ds, int t) { // 不能改變傳入的陣列值，用傳值呼叫 for(int p : ps) { // 依序從 ps 之中讀取數字 p int target = abs(t - p); // 要找的目標差值 auto it = find(ds.begin(), ds.end(), target); // 在 ds 之中找 target if (it == ds.end()) return false; // 如果 target 不在 ds 之中，回傳 false 跳出 dfs ds.erase(it); // 已找到 target，從 ds 之中移除 target } ps.push_back(t); // t 是符合要求的數字，將 t 加入 ps if (ds.empty()) { // 如果 ds 是空的，已經沒有要找的數字，結束 dfs sort(ps.begin(), ps.end()); // 將 ps 由小到大排序 imin = ps; // 更新 imin return true; // 回傳 true 結束 dfs } t = ds.back(); // t 改成目前 ds 中最後一項 if (dfs(ps, ds, last-t)) return true; // 遞迴，last-t 是另一組解 else return dfs(ps, ds, t); // 遞迴，t 是另一組解 } int main() { ios::sync_with_stdio(0); cin.tie(0); int n; cin >> n; // 陣列共有 n 個數字，所有的數字都在 1 ~ 100 之間 if (n == 1) { // 特例 cout << "0\n0\n"; // 印出兩個 0 return 0; // 離開程式 } int m = n*(n-1)/2; // 差值數量 vector<int> diff (m); // 陣列中任意兩個數的差值 for(int i=0; i<m; i++) cin >> diff[i]; sort(diff.begin(), diff.end()); // 由小到大排序 imin.resize(n); // 調整 imin 的大小 fill(imin.begin(), imin.end(), 1000); // 預設為於題目範圍的 n 個 1000 vector<int> points = {0}; // 答案中一定有 0 last = diff.back(); // diff 之中最後一項，最大的差值 dfs(points, diff, last); // 呼叫 dfs 求解 for(int i=0; i<n; i++) cout << imin[i] << " \n"[i == n-1]; // 印出答案 for(int i=n-1; i>=0; i--) cout << last-imin[i] << " \n"[i == 0]; return 0; } ``` <br /> --- ###### tags:`APCS`、`Python`、`C++`