# APCS 2025/01
## [第一題 等紅綠燈](https://zerojudge.tw/ShowProblem?problemid=q181)
a + b是紅綠燈的一個週期，所以x % (a + b)是那個循環的第?秒，所以判斷他是在綠燈的時候或是在等紅燈時。

#include <bits/stdc++.h>
using namespace std;
int main() {
	int a, b;
	cin >> a >> b;
	int t, ans = 0;
	cin >> t;
	while (t--) {
		int x;
		cin >> x;
		x %= (a + b);
		if (x >= a) ans += a + b - x;
	}
	cout << ans;
}

## [第二題 字串操作](https://zerojudge.tw/ShowProblem?problemid=q182)
這題很簡單，照著題目敘述去做就好。

#include <bits/stdc++.h>
using namespace std;
int main() {
	string s;
	cin >> s;
	int t;
	cin >> t;
	int n = s.size();
	while (t--) {
		int x;
		cin >> x;
		if (x == 0) {
			for (int i = 1;i < n;i += 2) swap(s[i], s[i - 1]);
		}
		if (x == 1) {
			for (int i = 1;i < n;i += 2) {
				if (s[i] < s[i - 1]) swap(s[i], s[i - 1]);
			}
		}
		if (x == 2) {
			string a = s;
			for (int i = 0, j = 1;j < n;i++, j += 2) {
				s[j - 1] = a[i];
				s[j] = a[i + n / 2];
			}
		}
	}
	cout << s;
}

## [第三題 重組問題](https://zerojudge.tw/ShowProblem?problemid=q183)
先記錄每個距離出現的次數，然後利用 dfs 函式找出可能的數列組合。dfs(l, r) 的作用是確定位置 l ~ r 的數字，而正在尋找的數字有兩種可能：

1. now 陣列中最大的數字減去 cnt 陣列中不為 0 的最大值。
2. cnt 陣列中不為 0 的最大值。

接著，使用 check 函式檢查這個數字是否符合條件。如果符合，就繼續對下一個數字進行 dfs 搜索。搜尋結束後，必須在回溯時將 check 中減去的 cnt 值補回去，以確保後續遞迴的正確性。

當 l > r 時，表示所有數字都已確定，因此將當前的數列分別與 ma 和 mi 取最大值與最小值，以確定最終的字典序排列。

#include <bits/stdc++.h>
using namespace std;
int cnt[101] = {};
int n;
vector<int> ma, mi, now;
int find() {
	for (int i = 100;i >= 0;i--) {
		if (cnt[i]) return i;
	}
	return -1;
}
bool check(int l, int r, int x) {
	bool flag = 1;
	for (int i = 0;i < l;i++) {
		if (--cnt[abs(now[i] - x)] < 0) flag = 0;
	}
	for (int i = n - 1;i > r;i--) {
		if (--cnt[abs(now[i] - x)] < 0) flag = 0;
	}
	return flag;
}
void back(int l, int r, int x) {
	for (int i = 0;i < l;i++) {
		cnt[abs(now[i] - x)]++;
	}
	for (int i = n - 1;i > r;i--) {
		cnt[abs(now[i] - x)]++;
	}
}
void dfs(int l, int r) {
	if (l > r) {
		mi = min(mi, now);
		ma = max(ma, now);
		return;
	}
	int big = find();
	now[l] = now[n - 1] - big;
	if (check(l, r, now[l])) dfs(l + 1, r);
	back(l, r, now[l]);
	now[r] = big;
	if (check(l, r, now[r])) dfs(l, r - 1);
	back(l, r, now[r]);
}
int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	cin >> n;
	if (n == 1) {
		cout << 0 << '\n' << 0 << '\n';
		return 0;
	}
	for (int i = 0;i < n * (n - 1) / 2;i++) {
		int x;
		cin >> x;
		cnt[x]++;
	}
	ma.assign(n, 0);
	mi.assign(n, 100);
	now.assign(n, 0);
	now[n - 1] = find();
	cnt[now[n - 1]]--;
	dfs(1, n - 2);
	for (int i = 0;i < n;i++) cout << mi[i] << ' ';
	cout << '\n';
	for (int i = 0;i < n;i++) cout << ma[i] << ' ';
}

## [第四題 分組開會](https://zerojudge.tw/ShowProblem?problemid=q184)
由於這題的最大n為2×10^5^，所以無法使用O(n^2^)的解法。我們採用更高效的方法，一邊計算最小移動距離，一邊維護最佳答案。

計算最小移動距離的方法如下：
1. 找出這組的中位數（即排序後的第k/2個元素）。
2. 計算左右兩部分的總移動距離：
右半部分的總和 減去 左半部分的總和，即該組數列調整成中位數所需的總距離。

在每次檢查時，我們都額外考慮一種情況：
將最小移動距離加上 k，並與當前最佳答案 ans 取最小值，以確保找到全局最優解。

#include <bits/stdc++.h>
using namespace std;
#define int long long
vector<int> p;
int f(int a, int b) {
	return p[b] - p[a - 1];
}
signed main() {
	int n, k;
	cin >> n >> k;
	p.assign(n + 1, 0);
	vector<int> v(n);
	for (int i = 0;i < n;i++) cin >> v[i];
	sort(v.begin(), v.end());
	for (int i = 0;i < n;i++) p[i + 1] = p[i] + v[i];
	int MIN = 1e18, ans = 1e18;
	int h = k / 2;
	for (int i = k;i + k <= n;i++) {
		MIN = min(MIN, f(i - h + 1,i) - f(i - k + 1, i - k + h));
		ans = min(ans, MIN + f(i - h + k + 1, i + k) - f(i + 1, i + h));
	}
	cout << ans;
}