---
title: 'APCS 2025/01 實作題題解 — C++'
disqus: hackmd
---

# APCS 2025/01 實作題題解 — C++
:::info
:bulb: 此筆記為APCS 2025年01月實作題考試的題目詳解。每一題的題解都包含解題思路、C++範例程式碼。
:::

## 第一題 等紅綠燈 (ZeroJudge q181.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q181)
:::success
操場起跑線上有一個紅綠燈，綠燈為 $a$ 秒，紅燈為 $b$ 秒，依照綠燈紅燈的順序循環。 有 $n$ 個小朋友，從操場的起跑線騎腳踏車一起起跑，他們分別騎完一圈的時間為 $t_1, t_2, ..., t_n$。若騎到終點時為紅燈，需要等待紅燈結束變為綠燈才可以停止騎車。 求出這 $n$ 個小朋友共需要等待幾秒的紅燈秒數。

:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題不需要用陣列，我用 people 當作每個小朋友騎行的時間。
wait = people % cycle - a 可得出小朋友騎到時省下的時間，有幾種狀況：
1. wait < 0：騎到紅綠燈時，剛好是綠燈可以直接通過
=> wait 設為 0
2. wait = 0：騎到紅綠燈時，剛好是綠燈轉紅燈，需要完整停一次紅燈時間
=> wait 設為 b
3. wait > 0：騎到紅綠燈時，紅燈已經過 wait 秒
=> wait 設為 b - wait (原本代表的省下的時間)

最後用 total 紀錄所有小朋友等待的時間的總和。
:::

### 範例程式碼

#include <iostream>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, a, b, n, cycle, people, wait, total = 0;
	
	cin >> a >> b >> n; 

	cycle = a + b;  //綠燈 + 紅燈的週期 

	for (i=0;i<n;i++) {
		cin >> people;  //騎行時間 
		
		wait = people % cycle - a;  //省下的等待時間 
		
		if (wait < 0)  //綠燈時通過 
			wait = 0;  //無需等待
		else
			wait = b - wait;  //需等待的紅燈時間 
			
		total += wait;  //總等待時間 
	}
	
	cout << total;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (3ms, 348KB)

## 第二題 字串操作 (ZeroJudge q182.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q182)
:::success
給一個字串 $S$，有三種字串操作，分別如下
1. 兩兩交換：將字串內相鄰兩個字元交換，例如字串 "apcsntnu" 先分組成 (ap)(cs)(nt)(nu)，將會交換為 (pa)(sc)(tn)(un)，即得到 "pasctnun"。
2. 兩兩排序：將字串內相鄰兩個字元按照字典序排序，字元的字典序為 a < b < ... < z，例如字串 "family" 先分組成 (fa)(mi)(ly)，將會交換成 (af)(im)(ly)，即得到 "afimly"。
3. 完美重排：假設字串長度為 $n$，將字串內的字元編號為 $0, 1, 2, ..., n-1$，將字串分成兩半為 $0, 1, ..., \frac{n}{2}-1$ 和 $\frac{n}{2}, \frac{n}{2}+1, ..., n-1$，並且組合成 $0, \frac{n}{2}, 1, \frac{n}{2}+1, ..., \frac{n}{2}-1, n-1$。例如 "apcsntnu" 拆成 "apcs" 和 "ntnu"，然後交錯成 "anptcnsu"。

給定 $k$ 個操作，請依序操作字串，輸出最後的字串結果。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
直觀的去解就可以了。

我分別用 exchange、sorting、rearrange 三個函式分別代表三個種類，為兩兩交換、兩兩排序、完美重排的用途。

1. 兩兩交換
就是直接用迴圈迭代，將兩兩互換，然後 i 一次加二。
2. 兩兩排序
用 1. 的方法加上條件判斷，當 s[i] > s[i+1]，也就是前面的字元的字典排序較後（例如 s[i] = 'b' > 'a' = s[i+1]）就互換，否則保持原樣。
3. 完美重排
用 temp 存原本的字串（若用同字串排列會出問題），再用 m = n / 2 取得字串的一半長度，num 代表新的字串的已排序長度，然後取得 s[num] = temp[i] 為前半字串新的字元排序 s[num+1] = temp[m+i] 為後半字串新的字元排序，這樣就可以達到原本要的 $0, \frac{n}{2}, 1, \frac{n}{2}+1, ..., \frac{n}{2}-1, n-1$ 的交錯排序。
:::

### 範例程式碼

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

string exchange(int n, string s)
{
	int i;
	char temp;
	
	for (i=0;i<n;i=i+2) {
		temp = s[i];
		s[i] = s[i+1];
		s[i+1] = temp;
	}
	
	return s;
}

string sorting(int n, string s)
{
	int i;
	char temp;
	
	for (i=0;i<n;i=i+2) {
		if (s[i] > s[i+1]) { 
			temp = s[i];
			s[i] = s[i+1];
			s[i+1] = temp;
		} 
	}
	
	return s;
}

string rearrange(int n, string s)
{
	string temp = s;
	int i, m = n / 2, num = 0;  //m為s字串一半的長度, num 存已更新的長度 
	
	for (i=0;i<m;i++) {
		s[num] = temp[i];  //前半字串 
		s[num+1] = temp[m+i];  //後半字串
		
		num = num + 2;
	}
	
	return s;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	string s;
	int i, n, k, category;
	
	cin >> s;
	
	n = s.size();  //字串長度 
	
	cin >> k;
	
	for (i=0;i<k;i++) {
		cin >> category;  //指令類別
		
		if (category == 0)  //兩兩交換 
			s = exchange(n, s);
		else if (category == 1)  //兩兩排序
			s = sorting(n, s);
		else  //完美重排 
			s = rearrange(n, s);
	}
	
	cout << s;

	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (3ms, 48KB)

## 第四題 分組開會 (ZeroJudge q184.)
### [題目](https://zerojudge.tw/ShowProblem?problemid=q184)
:::success
有 $n$ 個人在一個數線上，他們的位置座標分別為 $x_1, x_2, ..., x_n$
。今天要從 $n$ 個人中選出 $2k$ 個人開兩場會議，每一場會議要恰好 $k$ 個人參與，並且每一個人最多只能參與一個會議。

若一個人位在 $x$，欲前往 $y$ 處開會需要 $|x-y|$。請求出安排這兩場會議，使得參與會議的人移動距離總和最小值為何。
:::

### 輸入 / 輸出說明
| **輸入說明** | **輸出說明** |
|:-:|:-:|
|  |  |

### 解題思路
:::warning
這題要記得用 long long int 才會過。
詳細過程如範例程式碼，我有註解了，這邊只說核心演算法。

中位數求法標準解法是：
1. 若個數為奇數
最中間的數值即是中位數，值為這題的 $\frac{k-1}{2}$ 的值
2. 若個數為偶數
最中間的數值即是中位數，值為這題的 $\frac{k-1}{2}$ 與 $\frac{k-1}{2}+1$ 的值的 $\frac{1}{2}$

因為這題主要是要算與中位數之間的差，這題偶數可以直接用 $\frac{k-1}{2}$ 就可以了，不需要取中間兩數平均，方便程式設計

成本算法（滑動視窗）：
用滑動視窗法的去求出 i ~ i + (k - 1) 需要的成本，就是每個人跟中位數的距離（最短距離總和），接著每次中位數往右滑動一位，然後做以下動作：
1. 左邊的成本總和減去原本最左邊的人與原中位數的距離，因為成員不再有他了
2. 新中位數與舊中位數的差就是每個左邊還在的人需要增加的距離，乘上人數，左邊的成本總和減去他
3. 右邊的成本總和加上新的最右邊的人與新中位數的距離，是新增加的成員
4. 新中位數與舊中位數的差就是每個右邊還在的人需要減少的距離，乘上人數，右邊的成本總和減去他

最小組合算法：
迭代求最左邊到 i 的最小成本，以及 i 到最右邊的最小成本，最後求兩者相加的總體成本
:::

### 範例程式碼

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	int i, j, n, k, med;
	
	cin >> n >> k;
	
	long long int x[n], cost[n-k+1], minv = 9e18;
	long long int left_total = 0, right_total = 0, add, minus;
	
	for (i=0;i<n;i++)
		cin >> x[i];
	
	sort(x, x + n);  //x 陣列排序 
	
	//=== 第一組 0 ~ k - 1 === 
	//偶數的中位數這個跟中間兩個取平均的方法答案一樣 
	med = (k-1) / 2;  //取中位數 
	//得到 cost[0]，是 0 ~ k - 1 的成本總和 
	for (i=0;i<med;i++)  //中位數左邊的成本總和 
		left_total += x[med] - x[i];
	for (i=med+1;i<k;i++)  //中位數右邊的成本總和 
		right_total += x[i] - x[med]; 
	//cost[0]，0 ~ k - 1 的成本總和  
	cost[0] = left_total + right_total; 
		
    	//=== 其餘組 === 
	for (i=1;i<=n-k;i++) {
		med++;  //中位數右移
		left_total -= x[med-1] - x[i-1];  //刪除最左邊的成本
 		right_total += x[i+k-1] - x[med];  //新增最右邊的成本 
		
		//中位數左邊的成本總和更新
		add = x[med] - x[med-1];  //需要補上的成本 (原中位數與新中位數的差) 
		left_total += add * ((k-1)/2);
		//中位數右邊的成本總和更新
		minus = x[med] - x[med-1];  //需要減去的成本 (原中位數與新中位數的差，負的) 
		right_total -= minus * (k - 1 - (k-1)/2);
		
		cost[i] = left_total + right_total;  //cost[i]，i ~ i + k - 1 的成本總和  
	}
		
	//求最小組合
	long long int best_left[n-k+1], best_right[n-k+1];
    
	best_left[0] = cost[0];  //最左邊成本 
	for (i=1;i<=n-k;i++)
        	best_left[i] = min(best_left[i-1], cost[i]);  //求最左邊到 i 的最小成本  
    
	best_right[n-k] = cost[n-k];  //最右邊成本 
    	for (i=n-k-1;i>=0;i--)
        	best_right[i] = min(best_right[i+1], cost[i]);  //求 i 到最右邊的最小成本  
    
    	for (i=0;i<=n-2*k;i++)
        	minv = min(minv, best_left[i] + best_right[i+k]);  //求整體成本 
    
    	cout << minv;

    	return 0;
}

### 運行結果
<font color="#00BB00">**AC**</font> (57ms, 6.4MB)

###### tags: `APCS實作題`

:::danger
查看更多資訊請至：https://www.tseng-school.com/
:::