APCS 2025.01實作題題解 –- C++與Python

在這份筆記中，我們說明APCS 2025年1月實作題考試的題目解說。這些題目是根據ZeroJudge上的版本，與真實考試的版本題意應該是一樣的，但題目敘述、測資與環境並不一定相同。

每一題的題解都包含題意分析、演算法、C/C++範例程式與Python範例程式。其中後兩個單元是獨立的，也就是必要的說明會在兩個單元重複出現，為了方便有些人只看其中一種語言。

第一題 等紅綠燈 (ZeroJudge q181)

題意分析

(題目連結)等紅綠燈
操場起跑線上有一個紅綠燈，綠燈為

$a$秒，紅燈為

$b$秒，依照綠燈紅燈的順序循環。 有

$n$位小朋友，從操場的起跑線騎腳踏車在綠燈開始時一起起跑，每一位小朋友若騎到終點時為紅燈，需要等待紅燈結束變為綠燈才可以結束。
求出這

$n$位小朋友共需要等待幾秒的紅燈秒數。

演算法構思與程式流程

有

$n$位小朋友，但他們每一個人的等待時間是獨立無關的，所以只要會求每一位小朋友的等待時間，跑一個迴圈把它們加起來就是答案。
第一子題只有一位小朋友，所以不需要迴圈，只要會求一位的等待時間就是答案。重點是如何計算一位小朋友的等待時間。

綠燈與紅燈以

$a$與

$b$的時間週期循環，所以一次循環的週期是

$a+b$，也就是說，如果經過

$t$秒回到起點，那麼就是在綠燈開始後

$w=t\mathrm{\%}(a+b)$到達。等待時間分成兩種狀況：

• $w<a$，此時是綠燈的期間，無需等待。所以等待時間是0。
• $w\ge a$，此時是紅燈，需要等到紅燈結束，等待時間是
  $a+b-w$。

C/C++範例程式

先看第一子題的解，也就是計算一位小朋友的等待時間。雖然第一子題綠燈與紅燈的秒數固定是10秒，我們只要能讀入跑一圈的秒數就能夠進行計算。不過根據題目的輸入格式，在程式中我們還是必須把所有輸入的參數讀進來。
我們需要設計以下變數來儲存資料：

• green：綠燈秒數
• red：紅燈秒數
• n：小朋友人數
• t：騎一圈的秒數
  除此之外，我們設計以下變數來存放計算過程與結果：
• period：紅綠燈循環一次的週期
• wait：等待時間

本題C與C++寫法的差別只有在標頭檔與輸入輸出指令，我們寫在同一個程式中，scanf與printf的用法在註解中。以下是第一子題的範例程式。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,green,red,t,wait;
    cin >> green >> red >> n; // scanf("%d%d%d",&green,&red,&n);
    int period=green+red; // period time of green and red light
    cin >> t; //scanf("%d",&t); read time of one round
    t %= period; // elapsed time from start of green
    if (t < green) { // in green light, no wait
        wait = 0;
    } else { // in red, wait
        wait = period-t; // until next green
    }
    cout << wait << '\n'; //printf("%d\n",isum);
    return 0;
}

完全解的寫法只差在需要一個迴圈把每一位小朋友的等待時間加總。除了上述變數外，我們需要一個紀錄總和的變數isum，記得要給初值0，這是很多初學者容易犯的錯誤。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, i,green,red,t,wait,isum=0;
    cin >> green >> red >> n; //scanf("%d%d%d",&green,&red,&n);
    int period=green+red; // period time of green and red light
    for (i=0;i<n;i++) { // for each kid
        cin >> t; //scanf("%d",&t); // read time of one round
        t %= period; // elapsed time from start of green
        if (t < green) { // in green light, no wait
            wait = 0;
        } else { // in red, wait
            wait = period-t; // until next green
        }
        isum += wait; // total waiting time
    }
    cout << isum << '\n'; //printf("%d\n",isum);
    return 0;
}

Python範例程式

使用Python考APCS的人需要對list與迴圈有基本認識以方便處理輸入，否則幾乎無法做題目，以下面的程式前三行為例，第一行是一行數入兩個整數，第二行是一行輸入一個整數，第三行是一行輸入若干個以空白間隔的整數，這些是常用的方法，必須一記。

雖然第一子題綠燈與紅燈的秒數固定是10秒，我們只要能讀入跑一圈的秒數就能夠進行計算。不過根據題目的輸入格式，在程式中我們還是必須把所有輸入的參數讀進來。這裡我們假設讀者具備基本的變數、list與迴圈的能力，所以不單獨說明第一子題的解，直接說明完全解。

我們需要設計以下變數來儲存資料：

• green：綠燈秒數
• red：紅燈秒數
• n：小朋友人數
• t：騎一圈的秒數
  除此之外，我們設計以下變數來存放計算過程與結果：
• period：紅綠燈循環一次的週期
• wait：等待時間
• isum：等待時間的總和

程式就直接依照上述定義好的變數來做就可以了，注意第6行以迴圈依序歷遍列表中每一個元素的寫法。

green,red = [int(x) for x in input().split()]
n = int(input())
p = [int(x) for x in input().split()]
isum = 0 # total wait
period = green+red # period time 
for t in p: # time of each kid 
    t %= period # elapsed time from start of green
    if t < green: # in green, no wait
        wait = 0
    else: #in red, wait until end of red
        wait = period-t
    isum += wait # summed to total waiting time 
#
print(isum)

第二題 字串操作 (ZeroJudge q182)

題意分析

(題目連結) 字串操作

給一個字串，有三種字串操作，分別如下

0. 兩兩交換：每兩個字元一組，將字串內每一組的兩個字元交換，例如字串 "apcsntnu" 先分組成 (ap)(cs)(nt)(nu)，將會交換為 (pa)(sc)(tn)(un)，即得到 "pasctnun"。
1. 兩兩排序：每兩個字元一組，將字串內每一組的兩個字元按照字典序排序，字元的字典序為 a < b < … < z，例如字串 "family" 先分組成 (fa)(mi)(ly)，將會交換成 (af)(im)(ly)，即得到 "afimly"。
2. 完美洗牌：假設字串內的字元編號由0開始，字串等分為左右兩半，左邊依序放在新字串的第
   $0,2,4,\dots$的位置，而右半部依序放在新字串的第
   $1,3,5,\dots$的位置。例如 "apcsntnu" 拆成 "apcs" 和 "ntnu"，然後交錯成 "anptcnsu"。

給定

$k$個操作，請依序操作字串，輸出最後的字串結果。
第一子題只有一次完美洗牌的操作。

演算法構思與程式流程

這就是個字串的模擬操作題目，只要依照定義進行操作就可以。不過字串在C、C++與Python的處理方式都不一樣，必須熟悉自己所使用語言中有關陣列或字串的操作指令。
第一子題只有一個操作而且一定是完美洗牌，其實前兩個操作兩兩交換與兩兩排序都比較容易，洗牌的操作可能有些人容易迷惑，我們先看完美洗牌的流程，主要有兩種思考方式，只要會其中一種就可以。

完美洗牌的流程(一) -- 以目的字串來自何處來思考：
假設要洗牌的字串是S，排列後變成T，T的內容從前往後是交叉由S左半部與S右半部而來。
1. 將字串S均等分成左右兩半left與right
2. for i from 0 to n/2-1 do
       將left[i]與right[i]放入T中

完美洗牌的流程(二) -- 以來源字串會洗到哪裡去來思考：
假設要洗牌的字串是S，排列後變成T，S的左半部與右半部從前往後會變成T的偶數位置與奇數位置。
1. 將字串S均等分成左右兩半left與right
2. for i from 0 to n/2-1 do
       將left[i]放入T[2i]
3. for i from 0 to n/2-1 do
       將right[i]放入T[2i-1]	   

完全解的主要流程規劃如下：

主要流程
輸入字串S
輸入操作次數k
for i from 1 to k do
    讀入操作代號op
    if op == 0 then
        進行兩兩交換操作
    else if op == 1 then
        進行兩兩排序操作
    else
        進行完美洗牌操作
    endif
endfor
輸出結果

要留意操作過程可能會轉存在另外一個字串T，每次操作完存回到S。
細節因語言不同有不同做法，我們留在下節說明。

C/C++範例程式

第一子題只有一個操作而且一定是完美洗牌，先看C++的寫法。
C++的字串是用string來宣告，第8行之前是輸入，輸入後我們先宣告一個字串t，他會是個空的字串，然後我們用前述第一種思考的流程來做洗牌，s[i]就是左半部的第i個，s[n/2+i]就是右半部的第i個。

// subtask 1, one operation shuffle
#include <bits/stdc++.h>
using namespace std;
int main() {
    int k,op;
    string s;
    cin >> s >> k; // k==1
    cin >> op; // op==2 shuffle
    int n = s.length();
    string t;
    for (int i=0; i<n/2; i++) {
        t += s[i];
        t += s[n/2+i];
    }
    cout << t << '\n';
    /*
    string t(s); // copy s to t
    // shuffle t to s
    for (int from=0, to=0; from<n/2; from++, to+=2) {
        s[to] = t[from];
    }
    for (int from=n/2, to=1; from<n; from++, to+=2) {
        s[to] = t[from];
    }
    cout << s << '\n';
    */
    return 0;
}

這個程式碼中被註解掉的後半部是用第二種流程來寫的，也提供讀者參考。

以下介紹C的第一子題寫法，有些寫C++的人可能字串也會用C的方式來處理。C的字串是字元的陣列，有些時候指令會稍微麻煩一點，以下是C的第一子題寫法。
第8行直接宣告兩個字串，輸入放在s，操作後放在t。第14行的迴圈中，這裡用3個變數來記錄位置，i是t的位置，le是s左半部的位置，而ri是s右半部的位置。

後半部註解掉的部分是第二種思考流程的寫法，分兩個迴圈來處理s的左半部與右半部。

// subtask 1, one operation shuffle
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
int main() {
    int k,op;
    char s[N],t[N];
    scanf("%s%d",s,&k); // k==1
    scanf("%d",&op); // op==2 shuffle
    int n = strlen(s), from, to; // string length
    t[n] = '\0'; // end of string
    // modify to t, shuffle
    for (int i=0,le=0,ri=n/2; i<n; i+=2,le++,ri++) {
        t[i] = s[le];
        t[i+1] = s[ri];
    }
    /*
    for (from=0, to=0; from<n/2; from++, to+=2) {
        t[to] = s[from];
    }
    for (from=n/2, to=1; from<n; from++, to+=2) {
        t[to] = s[from];
    }
    */
    printf("%s\n",t);
    return 0;
}

接著來看完全解。先看C++的寫法。
依照前面介紹的主要流程來寫。兩兩交換的部分，第12 ~ 16行我們用傳統的三步驟基本寫法，C++有提供swap函數來做，但如果不記得的話用基本指令也很容易完成。
第18 ~ 22行是兩兩排序的操作，這裡是利用min與max函數取出後放回所需的位置。
第24 ~ 30行是完美洗牌的操作，跟前面第一子題的寫法略有不同，我們先宣告一個t字串，並將s的內容拷貝給他(第24行)，然後再將他洗牌搬回s，當然也可以用前面第一子題的方法。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,k,i,op;
    string s;
    cin >> s >> k;
    n = s.length();
    for (i=0; i<k; i++) { // each operation
        cin >> op;
        if (op == 0) {
            for (int le=0; le<n; le+=2) { // pairwise swap
                char ch=s[le];
                s[le] = s[le+1];
                s[le+1] = ch;
            }
        } else if (op == 1) { // pairwise sort
            for (int le=0; le<n; le+=2) {
                char cmin=min(s[le],s[le+1]),cmax=max(s[le],s[le+1]);
                s[le] = cmin;
                s[le+1] = cmax;
            }
        } else { // shuffle
            string t(s); // copy s to t, shuffle back to s
            for (int from=0, to=0; from<n/2; from++, to+=2) {
                s[to] = t[from];
            }
            for (int from=n/2, to=1; from<n; from++, to+=2) {
                s[to] = t[from];
            }
        }
    }
    cout << s <<'\n';
    return 0;
}

再來介紹C的完全解。依照前面介紹的主要流程來寫。C的字串是字元的陣列，不要忘記結尾有個字串結尾符號(第10行)。
兩兩交換的部分，第14 ~ 18行我們用標準的三步驟交換程序來寫。
第20 ~ 25行是兩兩排序的操作，第21 ~ 22行先取出兩者中較小與較大者，然後放回所需的位置。
第27 ~ 33行是完美洗牌的操作，我們將s的內容洗牌到t，然後用字串拷貝的函數抄回s。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 200
int main() {
    int k,op;
    char s[N],t[N];
    scanf("%s%d",s,&k);
    int n = strlen(s);
    t[n] = '\0'; // end of string
    for (int i=0; i<k; i++) { // for each operation
        scanf("%d",&op);
        if (op == 0) { // pairwise swap
            for (int le=0; le<n; le+=2) {
                char ch=s[le];
                s[le] = s[le+1];
                s[le+1] = ch;
            }
        } else if (op == 1) { // sort
            for (int le=0; le<n; le+=2) {
                char cmin=(s[le]<s[le+1])? s[le]: s[le+1], // min
                     cmax=(s[le]>s[le+1])? s[le]: s[le+1]; // max
                s[le] = cmin;
                s[le+1] = cmax;
            }
        } else { // shuffle s to t
            for (int from=0, to=0; from<n/2; from++, to+=2) {
                t[to] = s[from];
            }
            for (int from=n/2, to=1; from<n; from++, to+=2) {
                t[to] = s[from];
            }
            strcpy(s,t); // copy back to s
        }
    }
    printf("%s\n",s);
    return 0;
}

Python範例程式

Python的字串是個不可更改的物件，所以他的做法與C有很大的差別，但如果了解他的使用方式，操作指令算是很簡潔方便的。
第一子題只有一個操作而且一定是完美洗牌，來看Python的寫法。
第6與第7行取出s的左右兩半，然後就讓s變成空字串，以下用附加的方式逐步把左右半部的第i個放加到s的尾端就可以了(第10 ~ 11行)。這個迴圈有另外一個寫法放在註解掉的第9行，那是利用了zip這個函數，供參考。

s = input()
k = int(input()) # ==1
op = int(input()) # ==2
n = len(s)
#shuffle
left = s[:n//2]
right = s[n//2:]
s = ''
#for u,v in zip(left,right): s += u+v
for i in range(n//2):
    s += left[i]+right[i]

print(s)

再來介紹Python的完全解。主架構是依照前面介紹的主要流程來寫。Python的字串是個不可更改的物件，除了在尾端附加，我們不能去變動(刪除或更改)字串中間的內容。
我們有兩個方式來處理這個題目，一個是先將字串改成list，全部操作完畢後再將他轉回字串。以下是完全用字串來做，對於每一個操作，我們都重新建構出另外一個字串，再把他存回s以便進行下一個操作。

兩兩交換的部分，第7 ~ 10行我們用一個迴圈每次處理一對，注意到第9行我們放入t的順序與s中的位置相反，這就做到兩者交換的目的。操作完畢後第10行將他回給s。
第12 ~ 15行是兩兩排序的操作，與交換類似，我們先讓t是空字串，用一個迴圈每次處理一對，第14行先取出兩者中較小者再取較大者，附加到t的尾端。第15行也是把操作完畢後的字串回給s。
第17 ~ 21行是完美洗牌的操作，跟第一子題的寫法一樣。

s = input()
k = int(input())
n = len(s)
for i in range(k):
    op = int(input())
    if op==0: # swap
        t = ''
        for i in range(0,n,2):
            t += s[i+1]+s[i] # reverse i and i+1
        s = t
    elif op==1: #sort
        t = ''
        for i in range(0,n,2): # min then max
            t += min(s[i],s[i+1])+ max(s[i],s[i+1])
        s = t
    else: #shuffle
        left = s[:n//2]
        right = s[n//2:]
        s = ''
        for u,v in zip(left,right): s += u+v
        #for i in range(n//2): s += left[i]+right[i]
    #
#
print(s)

第三題 重組問題 (ZeroJudge q182)

題意分析

(題目連結) 3. 重組問題
有一個遞增整數序列

$A=(a_1=0,a_2,\dots a_n)$，已知

$\mathrm{\Delta }$ 為陣列中任兩個數字的絕對值差所組成的一群數字。給定

$\mathrm{\Delta }$的內容，輸出可以生成該

$\mathrm{\Delta }$ 的最小與最大字典序

$A$序列。
舉例來說，如果n = 3且 ∆ = (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)。

第一子題

$n\le 6$，可以用效率比較差的方法做，完全解

$n\le 25$，需要比較好的方法。

演算法構思與程式流程

題目就是要找出字典序最小與最大(或是所有)可能的A序列，滿足他的距離差是輸入的(距離陣列)

$\mathrm{\Delta }$。
以下說明時，我們可以把A序列看成數線上的n個點，除了給定的第一點

$a_1=0$，要做的就是決定其它

$n-1$個點，這個題目看起來難理解，即使第一子題n比較小，也有無從下手的感覺。思考重點在題目中舉例所給的提示。首先，最大的數

$a_n$一定是距離陣列中的最大值，這個蠻明顯的。因此，我們已知我們知道最左邊的是0，最右邊的是

$a_n$，其它需要的點都在兩者之間。其次，在剩下的距離陣列中的最大值如果是d，那麼必然有一個點是d或者

$a_n-d$，是哪一個呢? 我們暫時無法決定，需要根據距離陣列來檢查，對於任何一種可能，他與已知點的距離必須在距離陣列中，如果不滿足此要求，那就是不可能；如果滿足，這個點目前暫時是可能的，可以依照這個程序在往下搜尋可能的下一點。
所以這是個遞迴暴搜的程序，設計遞迴程序可能有多種方式，通常遞迴程序中有三個部份：

1. 終端情形：遞迴到最後的情形，也就是找到了一個解。本題中，在終端情形時，我們需要檢查找到的解是否為最小與最大的序列。
2. 檢查是否合法：對於目前的點是否合於要求，如果不合，就放棄此解；如果合，就繼續下去。這個部分有時稱為剪枝。
3. 遞迴呼叫。

遞迴暴搜的寫法可以寫成「先檢查再呼叫」或者是「先呼叫再檢查」，兩種都是可以的，筆者本人的經驗習慣順序是「剪枝+終端+呼叫」。本題中，我們的遞迴程序規劃如下：

// 遞迴暴搜DFS
// p是已知點的陣列，d是距離陣列，q是目前想要加入的點
dfs(p, d, q) 
    檢查q與已知點的距離是否皆在d中，若否，則結束；若是，則d中刪除那些距離；
    將q放入p中；
    if d為空 then // 終端情形
        更新最小與最大的解；
        結束；
    end if
    找出d中的最大值，令他是q;
    遞迴呼叫 dfs(p, d, q);
    遞迴呼叫 dfs(p, d, last-q);  // last是最右邊的點
// end of dfs

我們主程序可以規劃如下：

// 主程序
輸入n與距離矩陣d
last = max(d); // d中最大值，是最右邊的點
p = [0]; // p是目前已知點，先設為只有第一點0
imin = [1000]; // 已經找到的最小序列，初設為不可能的大
imax = [-1]; // 已經找到的最大序列，初設為不可能的小
dfs(p, d, last); //檢查last是否為可能的點，若是，則以遞迴dfs繼續搜尋
輸出imin與imax;

上述程序中，我們可以看到有幾個實作上要求：

• 要在陣列中尋找某個值，檢查是否找到，並將其刪除。這部分有多種做法，線性搜尋或保持排序或是使用特別的資料結構。本題這個部分對時間的影響不大(陣列很小)，我們可以用最簡單的線性搜尋。
• 要在遞迴副程式中傳遞陣列。這個也有很多做法，而且每種語言(C, C++, Python)都有些差異。我們在下節實作中說明。

時間複雜度：因為只有n-2個點需要決定，粗略估計遞迴需要

$O(2^{n-2})$次，本題n不超過25，是沒有問題的。事實上，因為剪枝的關係，遞迴次數遠低於此，目前知道的最差狀況不超過

$O(2^{n/2})$次。
註：一般的遞迴暴搜題，剪枝可能可有可無，剪枝帶來的效率提升其實是非常難估算的。但本題的剪枝是必要的，因為距離陣列的長度是n(n-1)/2，如果全部都拿來枚舉，那只能通過第一子題。
註：本題因為只要找出最小與最大的序列，還有一個做法是找出最小的序列，因為最大的序列必然是最小序列的左右對稱解，也就是把所有的點v改成last-v所構成的序列。不過這個解法對考試並非必須的，且在考試時未必能想到，我們在下節中會揭示這個版本。

C/C++範例程式

先看C++的寫法。我們使用vector 來存放陣列，C++ vector允許一些簡單的操作如比較大小、複製以及刪除元素，寫起來會比較簡單，否則這些都需要自己寫。全域變數last是放最右邊的點，imin與imax是目前找到的最小與最大序列。
dfs傳入的陣p與d，本題因為陣列會被修改，我們用pass by value的方式整個copy進來，這樣比較方便，而且不容易出錯。第9 ~ 13行做檢查距離與剪枝的動作，對p中每一個既存點x，看看與q的距離abs(x-q)是否在d中，若否，則直接return，也就是q是不合法的，放棄此搜尋，否則，我們在d中刪除此距離。如果對全部的既存點都通過檢查，q就是可以放進來的(第14行)。
第15 ~ 20行是終端情形，我們要先將p排序，然後更新imin與imax。
第21行我們取出d中剩餘的最大值(d永遠保持排序好的狀態)，然後進行兩次遞迴呼叫，一次是以q為新的點，另一次則以last-q為新的點。

再看主程式的部分。第29行是一個特判n=1的情形，接著輸入距離陣列並排序，接著找出最大值，並設定初始的既存點。第38行遞迴呼叫後，就輸出答案。

#include <bits/stdc++.h>
using namespace std;
vector<int> imax(30,0), imin(30,1000);
int last;
// insert q into p and recursive if q can be a point
// (existing point, distances, new point)
void dfs(vector<int> p,vector<int> d,int q) {
    // check if q is a point
    for (int x:p) {
        auto it=find(d.begin(),d.end(),abs(x-q));
        if (it==d.end()) return; // distance not found
        d.erase(it);
    }
    p.push_back(q); // insert q as an existing point
    if (d.empty()) { // terminal case, update min and max
        sort(p.begin(),p.end());
        if (p>imax) imax = p;
        if (p<imin) imin = p;
        return;
    }
    q = d.back(); // remaining max distance
    dfs(p,d,q); // case 1, q is a point
    dfs(p,d,last-q); // case 2 last-q is a point
    return;
}
int main() {
    int n;
    scanf("%d",&n);
    if (n==1) { // special case
        printf("0\n0\n"); return 0;
    }
    int m=n*(n-1)/2;
    vector<int> d(m);
    for (int i=0;i<m;i++) scanf("%d",&d[i]);
    sort(d.begin(),d.end());
    last=d.back(); // max distance, last point
    vector<int> point({0}); // existing point 0
    dfs(point,d,last);
    // output
    for (int i=0;i<n;i++) {
        printf("%d%c",imin[i]," \n"[i==n-1]);
    }
    for (int i=0;i<n;i++) {
        printf("%d%c",imax[i]," \n"[i==n-1]);
    }
    return 0;
}

接著看C的寫法，這題C比較麻煩，一個原因是陣列的比較、複製、與刪除元素可能都要自己寫，排序的qsort也要寫比較函數。這些基本操作雖然不難，但是自己寫就增加了程式碼的長度。另外一個差異是C在副程式傳遞陣列時，是傳位置過去，因為遞迴呼叫會改變掉距離陣列的內容，所以我們要自己複製一份。
再者，C在陣列中刪除元素自己寫比較囉嗦，這裡我們改變一種方式，把刪除的距離改寫成不可能的-1，而並不將其移除。其它的流程與說明與前面C++程式差不多，就不再贅述。

// recursion, using c
#include <stdio.h>
#include <stdlib.h>
#define N 30
#define M 450
int imax[N], imin[N],last;
// compare func for qsort
int cmp(const void *x, const void *y) {
    return *(int*)x - *(int*)y;
}
// compare two array
int acmp(int n,int a[],int b[]) {
    for (int i=0;i<n;i++) {
        if (a[i]!=b[i]) return a[i]-b[i];
    }
    return 0;
}
// copy b to a
void cpy(int n,int a[],int b[]) {
    for (int i=0;i<n;i++) a[i]=b[i];
}

void dfs(int np,int nd,int p[],int d[],int q) {
    // check if distance to existing point
    int i,j;
    for (i=0;i<np;i++) { // for each point
        int mydist = abs(q-p[i]);
        for (j=0; j<nd; j++) {// linear search
            if (d[j]==mydist) break; // found
        }
        if (j>=nd) return; // not found
        d[j] = -1; // remove
    }
    // check successful
    p[np++] = q; // insert into existing point
    // find max remaining dist
    q = -1;
    for (i=0; i<nd; i++) {
        if (d[i]>q) q=d[i];
    }
    if (q < 0) { // terminal case, sol found
        qsort(p,np,sizeof(int),cmp);
        if (acmp(np,p,imax)>0) cpy(np,imax,p);
        if (acmp(np,p,imin)<0) cpy(np,imin,p);
        return;
    }
    int p2[N],d2[M]; // save array
    cpy(np,p2,p);
    cpy(nd,d2,d);
    dfs(np,nd,p2,d2,q); // case 1, q is a point
    dfs(np,nd,p,d,last-q); // case 2 last-q is a point
    return;
}
int main() {
    int k=0,i,j,n,m;
    scanf("%d",&n);
    if (n==1) { // special case
        printf("0\n0\n"); return 0;
    }
    imax[0]=-1;
    imin[0]=1001;
    m=n*(n-1)/2;
    int p[N]={0},d[M];
    for (i=0;i<m;i++) {
        scanf("%d",&d[i]);
    }
    qsort(d,m,sizeof(int),cmp);
    last = d[m-1];
    dfs(1,m,p,d,last);
    // output
    for (int i=0;i<n;i++) {
        printf("%d%c",imin[i]," \n"[i==n-1]);
    }
    for (int i=0;i<n;i++) {
        printf("%d%c",imax[i]," \n"[i==n-1]);
    }
    return 0;
}

這一題我們可以取個巧，因為數值範圍不超過100，我們可以用char來存放這些整數，這麼一來C的string.h中有些mem類的函數可以方便做陣列操作。此外，前面提到這題有一個方法是只找出最小序列，這裡我們用C的方式來說明這個方法。

除了mem函數之外，與前面的程式差異不大，但dfs程式改成回傳int，傳回1表示成功找到，傳回0表示沒有找到。注意第41 ~ 42行遞迴呼叫的地方，先嘗試以last-q呼叫，因為q是最大距離，這會找到比較小的序列，如果成功，就不再繼續搜；如果失敗才會嘗試q的呼叫。這樣寫找到的一定是最小序列，在第60行我們輸出他的對稱序列，必然為最大。

// recursion, using c string
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define N 50
#define M 1000
int rec_cnt=0;
char last,imin[N];
// compare func for qsort
int cmp(const void *x, const void *y) {
    return *(char*)x - *(char*)y;
}

// find the min
int dfs(int np,int nd,char p[],char d[],char q) {
    rec_cnt++;
    //printf("%d %d %d\n",np,nd,q);
    // check if distance to existing point
    int i,j;
    for (i=0;i<np;i++) { // for each point
        char mydist = abs(q-p[i]);
        char *ptr=memchr(d,mydist,nd);
        if (ptr==NULL) return 0; // not found
        *ptr = -1; // remove
    }
    // check successful
    p[np++] = q; // insert into existing point
    // find max remaining dist
    q = -1;
    for (i=0; i<nd; i++) {
        if (d[i]>q) q=d[i];
    }
    if (q < 0) { // terminal case, sol minimal found
        qsort(p,np,1,cmp);
        memcpy(imin,p,np);
        return 1;
    }
    char p2[N],d2[M]; // save array
    memcpy(p2,p,np);
    memcpy(d2,d,nd);
    if (dfs(np,nd,p,d,last-q)) return 1; // case 1 last-q is a point
    else return dfs(np,nd,p2,d2,q); // case 2, q is a point
}
int main() {
    int k=0,i,j,n,m,t;
    scanf("%d",&n);
    m=n*(n-1)/2;
    char p[N]={0},d[M];
    for (i=0;i<m;i++) {
        scanf("%d",&t);
        d[i] = (char)t;
    }
    last = d[m-1];
    if (!dfs(1,m,p,d,last)) fprintf(stderr,"No answer\n");
    // output
    for (int i=0;i<n;i++) {
        printf("%d%c",(int)imin[i]," \n"[i==n-1]);
    }
    // symmetry is max
    for (int i=n-1;i>=0;i--) {
        printf("%d%c",(int)(last-imin[i])," \n"[i==0]);
    }
    fprintf(stderr,"recursive all = %d\n",rec_cnt);
    return 0;
}

Python範例程式

以下介紹Python的範例。Python的陣列是用list來做，他的操作是很方便的
前兩行是輸入，第3行是一個特判n=1的情形。全域變數last是放最右邊的點，imin與imax是目前找到的最小與最大序列。
dfs傳入的list point與dist，分別是已經存在的點與目前剩下的距離陣列，q則是試圖新加入的點。第13 ~ 16行做檢查距離與剪枝的動作，對point中每一個既存點v，看看與q的距離abs(q-v)是否在dist中，若否，則直接return，也就是q是不合法的，放棄此搜尋，否則，我們在dist中刪除此距離。如果對全部的既存點都通過檢查，q就是可以放進來的(第18行)。
第19 ~ 23行是終端情形，我們要先將point排序，然後更新imin與imax。
第25行我們取出dist中剩餘的最大值(dist永遠保持排序好的狀態)，然後進行兩次遞迴呼叫，一次是以q為新的點，另一次則以last-q為新的點。本題因為list內容會被修改，傳遞時我們都將list複製一份後傳遞，這樣比較方便，而且不容易出錯。

主程式的後半段在第30行開始。遞迴呼叫後，就輸出答案。

n = int(input())
d = sorted([int(x) for x in input().split()])
if n==1: # special case
    print(0); print(0)
    exit(0)
imax = [0]*n # current max ans
imin = [1000]*n # current min ans
last = d[-1] # max, last point
p = [0] # existing point 0
# (existing point, distance, new point)
def dfs(point,dist,q): 
    global imin,imax
    for v in point: # check dist to existing point
        mydist = abs(q-v)
        if mydist not in dist: return 
        dist.remove(mydist)
    # check successful
    point.append(q) # add q to point
    if not dist: #empty, terminal case
        point.sort()
        imin = min(imin,point)
        imax = max(imax,point)
        return
    # recursive call, two cases,
    q = dist[-1] # max distance
    dfs(point[:], dist[:], q) # q is a point
    dfs(point[:], dist[:], last-q) #last-q is a point
    return
# main
dfs(p,d,last)
print(*imin)
print(*imax)

前面提到這題有一個方法是只找出最小序列，這裡我們來說明這個方法。
與前面的程式差異不大，但dfs程式改成會回傳True或False，傳回True表示成功找到，傳回False表示沒有找到。注意第24行遞迴呼叫的地方，先嘗試以last-q呼叫，因為q是最大距離，這會找到比較小的序列，如果成功，就不再繼續搜；如果失敗才會嘗試q的呼叫。這樣寫找到的一定是最小序列，在第31行我們輸出他的對稱序列，必然為最大。

n = int(input())
d = [int(x) for x in input().split()]
if n==1:
    print(0); print(0)
    exit(0)
imin = [1000]*n
last = d[-1]
p = [0]
# determined point, distance, new point
def dfs(point,dist,q): 
    global imin
    for v in point: # check dist to existing point
        mydist = abs(q-v)
        if mydist not in dist: return False
        dist.remove(mydist)
    # check successful
    point.append(q) # add q to point
    if not dist: #empty, terminal case
        point.sort()
        imin = point
        return True
    # recursive call, two cases,
    q = dist[-1] # max distance
    if dfs(point[:], dist[:], last-q): #last-q is a point
        return True
    else:
        return dfs(point[:], dist[:], q) # q is a point
# main
dfs(p,d,last)
print(*imin)
imax = [last-v for v in imin[::-1]]
print(*imax)

第四題 分組開會 (ZeroJudge q184)

題意分析

(題目連結) 4. 分組開會
有 n 個人在一個數線上，他們的位置座標分別為

$x_1,x_2,\dots ,x_n$。今天要從 n 個人中選出 2k 個人開兩場會議，每一場會議要恰好 k 個人參與，並且每一個人最多只能參與一個會議。
若一個人位在 x，欲前往 y 處開會需要 |x−y|。請求出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。

$2k\le n\le 2\times {10}^5$，座標值為不超過

${10}^9$的非負整數。

第一子題n ≤ 100。

演算法構思與程式流程

這個題目需要以下的思考：

• 每一組開會的人必然是座標排序後連續的一段，否則不會更好。證明其實很簡單，這算是個greedy觀念。
• 對於一組數字，要找一個p與這一群數字的距離和最小，那麼這群數字的中位數median是最佳的p點，奇數個數字時，中位數就是排序後正中間的點，例如(1, 3, 4)的話，選3。偶數個數字時，在正中間的兩個數之間的任何數字都是解，算出來答案一樣，例如(1, 3, 6, 9)，則3≤ p ≤ 6都是解。這個證明也很簡單，因為p的左右邊的數字數量如果不一樣，則將p往數量多的一邊移動的話距離總和會變小。

有了這兩點知識後之後，我們需要三個步驟：

1. 先把座標排序。
2. 計算出每一個長度為k的區間的最小成本，也就是該區間所有數字與其中位數的距離總和。
3. 找出成本和最小的兩個獨立區間。

以下分別說明後兩個步驟。

計算每一個區間的最小成本。
如果直接計算，那麼有n-k+1個區間，時間複雜度將會達到

$O(k(n-k+1))$，在k很大的時候將會是

$O(n^2)$。如何加速運算呢？方法不只一種，以下是一種所謂sliding window的方法。

因為所有區間都要計算，而每一個相鄰區間是非常相似的，區間[i-k+1,i]與下一個區間[i-k+2,i+1]只增減一個成員，所以我們可以去考慮兩者之間的差值，只要這個差值是可以很快算得出來，那麼就能夠節省全部的運算時間。
假設座標存在p，移動後的區間是[left, right]且中位數在med 而前一個已經算好的區間是[left-1, right-1]中位數在med-1。我們來考慮兩者的差異：

1. left-1 移出了區間，所以距離減少了p[med-1]-p[left-1]；
2. right移入了區間，所以距離增加了p[right]-p[med]；
3. 在[left, med-1]這些點，本來是連到p[med-1]，改成連到p[med]，每個點增加了p[med]-p[med-1]的距離；
4. 在[med, right-1]這些點，本來連到p[med-1]，改成連到p[med]，每個點減少了p[med]-p[med-1]的距離。

全部合計距離增加(p[right]-p[med])- (p[med-1]-p[left-1]) + (p[med]-p[med-1])*((med-1-left+1 – (right-1-med+1)) = (p[right]-p[med])- (p[med-1]-p[left-1]) + (p[med]-p[med-1])*(med+med-left– right)。
這個差值直接就可以在O(1)時間計算出來。

另外一種計算每個區間距離和的方法是利用前綴和。對於區間是[left, right]且中位數在med來說，右半部的點 med< i ≤ right，距離是p[i]-p[med]，總和是sum(p[med+1, right])-(right-med)*p[med]；左半部的點 left ≤ i < med的來說，距離是p[med]-p[i]，總和是(med-left)*p[med] – sum(p[left, med-1]])。若psum[i]是前i項的前綴和，兩者總和為
psum[right]-psum[med]-(psum[med-1]-psum[left-1])+p[med]*(med+med-left-right)
每個區間可以在O(1)完成計算。

計算兩個獨立區間的最小成本

假設我們要在一個數列中找總和最小的兩個元素，我們可以簡單地找出最小與第二小的數字即可。但是如果要找出兩個成本總和最小的獨立區間，就不能這麼簡單的找兩個最小成本的區間，因為找出來的兩個區間可能是有重疊的。
假設位置i是最佳解的第二個區間右端點，那麼第二個區間是[i-k+1,i]，而最佳解的第一個區間就是「右端<=i-k而成本最小的區間」。這樣可以保證兩個區間不重疊。如果對每一個i都算出這個最好的總和，從中取最小值就會是我們要的答案。
因此，我們可以對每一個位置i計算出成本其前綴最小值，也就是右端<=i的所有區間的最小成本，我們就可以很簡單的找到最小成本總和的兩個獨立區間。
這個方法算是一種簡單的DP觀念，有很多類似的題目都會用到這個方式。

整個計算流程如下：

座標排序
for i = k-1 to n-1 do
    計算[i-k+1, i]區間的距離總和放在d[i];
endfor
計算d的前綴最小值放在pmin;
best = oo;
for i = k+k-1 to n-1 do
    best = min(best, d[i]+pmin[i-k]);
end for
輸出best

時間複雜度是

$O(n\log n)$，除排序外都是

$O(n)$。

C/C++範例程式

這題想到方法後，實作並不困難，C與C++的寫法差不多，此處就不分兩個版本，以C++來示範。
準備三個陣列p, d, 與pmin放在全域變數，這題的數值可能很大，因此宣告為long long，避免運算過程溢位。輸入座標後，第12行排序(C的話需要使用qsort)，第17行先計算第一個區間的成本(距離總和)，我們用三個變數left, right, med記錄著左右端與中位數，雖然可以只用一個變數來做，其他兩個可以用運算得到，但多用兩個變數比較不傷腦筋，程式也清楚。
接著開始歷遍每一個區間，第19 ~ 23行計算出每一個區間的成本，這裡用的是sliding window計算差值的方式。
第25 ~ 26行計算成本的前綴最小值放在pmin，第30 ~ 31行計算出答案，最後，輸出答案。

// group median
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 200000
ll p[N],d[N],pmin[N];

int main() {
    int n, i,j,k;
    scanf("%d%d",&n,&k);
    for (i=0;i<n;i++) scanf("%lld",&p[i]);
    sort(p, p+n);
    // total distance of each group [left,right]
    int left=0,right=k-1,med=k/2; // median; right one for even k
    // distance of first group
    d[right] = 0;
    for (i=0; i<=right; i++) d[right] += abs(p[i]-p[med]);
    // sliding window to find distance of each group
    for (left++,right++,med++; right<n; left++,right++,med++) {
        d[right] = d[right-1]-(p[med-1]-p[left-1]); // move out
        // dif = p[med]-p[med-1]; // median move
        d[right] += (p[med]-p[med-1])*((med-left)-(right-med))+(p[right]-p[med]);
    }
    // prefix min of d
    pmin[k-1] = d[k-1];
    for (i=k; i<n; i++) pmin[i] = min(pmin[i-1],d[i]);
    // best of two group = min(d[i]+pmin[i-k])
    // last group at [i-k+1,i] and first group [, <= i-k]
    ll best = 1e16;
    for (i=k+k-1; i<n; i++) {
        best = min(best, d[i]+pmin[i-k]); // best two groups
    }

    printf("%lld\n",best);
    return 0;
}

Python範例程式

以下是Python的寫法。這題想到方法後，實作並不困難，前兩行輸入資料，第3行把座標排序，第7行先計算第一個區間的成本(距離總和)，接著開始歷遍每一個區間，第9 ~14行計算每一個區間的成本，我們用三個變數le, ri, med記錄著左右端與中位數，雖然可以只用一個變數來做，其他兩個可以用運算得到，但多用兩個變數比較不傷腦筋，程式也清楚。這裡用的是sliding window計算差值的方式。
第16 ~ 18行計算成本的前綴最小值放在pmin，第20行計算出答案，最後輸出答案。

n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
p.sort()
oo = 10**18
d = [oo]*n
# first group
d[k-1] = sum(abs(x-p[k//2]) for x in p[:k])
# sliding window for each group cost
le,med = 1,k//2+1
for ri in range(k,n):
    d[ri] = d[ri-1]-(p[med-1]-p[le-1])+p[ri]-p[med] + \
        (p[med]-p[med-1])*(med-le - (ri-med))
    le += 1
    med += 1
# best = min(last group at i and prev group before i-k) 
pmin = d[:]
for i in range(k,n): # prefix min
    pmin[i] = min(pmin[i],pmin[i-1]) 
# best of two groups 
best = min(d[i]+pmin[i-k] for i in range(k+k-1,n)) 
print(best)

下面我們也揭示第二種利用前綴和的成本計算方式，其餘部分則沒什麼改變。

n,k = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]
p.sort()
psum = p+[0] # as -1
for i in range(1,n):
    psum[i] += psum[i-1] # prefix sum
d = [0]*n
le,med = 0,k//2
dd = med+med-0-(k-1) # med+med-left-right, never change
for ri in range(k-1,n):
    d[ri] = psum[ri]-psum[med]-(psum[med-1]-psum[le-1])+p[med]*dd
    le += 1
    med += 1
# best = min(last group at i and prev group before i-k) 
pmin = d[:]
for i in range(k,n): # prefix min
    pmin[i] = min(pmin[i],pmin[i-1]) 
# best of two groups 
best = min(d[i]+pmin[i-k] for i in range(k+k-1,n)) 
print(best)

End