# APCS 202501 考後題解
算一種解討吧idk，但我都盡量自己寫
還有我那時候考225分，三級分，所以希望下次能考四或五

---

### 1. 等紅綠燈
> ZeroJudge q181
> https://zerojudge.tw/ShowProblem?problemid=q181

* 送分題，直接告訴你怎麼算lol
* 我5分鐘就寫完了

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

int a, b, n, num, counter;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> a >> b >> n;
    for (int i=1; i<=n; ++i){
        cin >> num;
        if (num%(a+b) >= a) counter += b-(num%(a+b)-a);
    }
    cout << counter << endl;
}

---

### 2. 字串操作
> ZeroJudge q182
> https://zerojudge.tw/ShowProblem?problemid=q182

* 一般來說這裡會是二維陣列的題目，只是這次換這一題簡單的bruh
* 敘述很直接，沒有要繞路特別想的地方
* 注意自己寫的有沒有對，很容易寫錯

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

string s; int n, op;
int main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> s >> n;
    for (int i=1; i<=n; ++i){
        cin >> op;
        if (op==0){
            for (int j=0; j<s.size(); j+=2) swap(s[j], s[j+1]);
        }else if (op==1){
            for (int j=0; j<s.size(); j+=2){
                if (s[j] > s[j+1]) swap(s[j], s[j+1]);
            }
        }else{
            string temp="";
            for (int l=0, r=s.size()/2; r<s.size(); ++l, ++r){temp += s[l]; temp += s[r];}
            s = temp;
        }
    }

    cout << s << endl;
}

---

### 3. 重組問題
> ZeroJudge q183
> https://zerojudge.tw/ShowProblem?problemid=q183

* 想不到 以後再說 :)

更新：
(我APCS歷屆就剩這題了 可以有人救一下嗎 :U)

---

### 4. 分組開會
> ZeroJudge q184
> https://zerojudge.tw/ShowProblem?problemid=q184

* 考點：sort、滑動窗口、dp、絕對值的運算(高一數學範圍)

#### **解法：**
* 首先要先sort(應該不用我講)
* 然後用一個滑動窗口去找窗口中最小的移動距離，並存到place裡面

---

* 最小移動距離**點**：

點為a~i~, a~i+1~, ..., a~i+k-1~，x為線上一點
則總移動距離為 f(x) = |x-a~i~| + |x-a~(i+1)~| + ... + |x-a~i+k-1~|
若我們要使f(x)有min直(最小的移動距離)
--若k為奇數，則 x=a~(i+(k-1)/2)~
--若k為偶數，則 a~(i+(k/2)-1)~<=x<=a~(i+(k/2))~
(偶數的我取a~(i+(k-1)/2)~，因為c++會把小數砍掉，會是比較小的那一個)

---

* 滑動窗口算下一個最小移動距離：
設上一個窗口的最小移動距離為x，中心點為n，現在的最小移動距離為y，中心點為m

--若k為奇數：y=x - (n-a~i-1~)-...-(a~(i+k-1)~-n) + (m-a~i~)+...+(a~(i+k-1)~-m)
n和m可以在兩個窗口內完全消掉，留下第一個窗口的一個(-m)和第二個窗口的一個(-n)
a~i~到a~(i+k-2)~都會互相削掉
留下來的就是 y=x+a~i-1~+a~(i+k-1)~-n-m

--若k為偶數 y=x - (n-a~i-1~)-...-(a~(i+k-1)~-n) + (m-a~i~)+...+(a~(i+k-1)~-m)
n和m可以在兩個窗口內消掉，留下第一個窗口的-(m-n)和第二個窗口的(-n-m)，可得(-2m)
a~i~到a~(i+k-2)~都會互相削掉
留下來的就是 y=x+a~i-1~+a~(i+k-1)~-2*m

---
* 從place取兩個不在同一個窗口內的最小值：

先存一個dp[i]，為到第i個前取一個最小的值
而再存一個mincount，為取兩個(第i項和前面不在同一個窗口內的)的min值
mincount = min(mincount, dp[i-k]+place[i])
mincount為答案

#include <bits/stdc++.h>
#define endl '\n'
#define maxn 200005
#define inf 1e18
#define int long long
using namespace std;

int n, k, nums[maxn], place[maxn], prevp, dp[maxn], mincount;
signed main(){
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> n >> k;
    for (int i=1; i<=n; ++i) cin >> nums[i];
    sort(nums+1, nums+1+n);

    prevp=nums[1 + ((k-1)/2)]; place[1] = 0;
    for (int i=1; i<=k; ++i) place[1] += abs(nums[i] - prevp);

    for (int i=2; i<=n-k+1; ++i){
        int mp=nums[i + ((k-1)/2)];

        //用數學去算
        if (k%2 == 0){
            place[i] = place[i-1] + nums[i-1] + nums[i+k-1] - 2*mp;
        }else{
            place[i] = place[i-1] + nums[i-1] + nums[i+k-1] - prevp - mp;
        }
        prevp = mp;
    }

    dp[1] = place[1]; mincount = inf;
    for (int i=2; i<=n-k+1; ++i){
        dp[i] = min(dp[i-1], place[i]);
        if (i>k) mincount = min(mincount, dp[i-k] + place[i]);
    }

    cout << mincount << endl;
}