2025 SCPC 4-1

1
#include <bits/stdc++.h>
2
using namespace std;
3
using ll = long long;
4

5
// 두 벡터의 총 거리 계산 함수
6
ll total_distance(const vector<int>& people, const vector<int>& stores) {
7
    ll sum = 0;
8
    for (size_t i = 0; i < people.size(); ++i) {
9
        sum += abs((ll)people[i] - stores[i]);
10
    }
11
    return sum;
12
}
13

14
int main() {
15
    ios::sync_with_stdio(false);
16
    cin.tie(nullptr);
17

18
    int T; // 테스트 케이스 수
19
    cin >> T;
20

21
    for (int test_case = 1; test_case <= T; ++test_case) {
22
        int N, R;
23
        cin >> N >> R; // 집과 빨간 집의 수 (R == 1)
24

25
        int blue_house_count = N - R;
26
        int red_house_count = R;
27

28
        int blue_store_count = N - R - 1;
29
        int red_store_count = R + 1;
30

31
        vector<int> blue_houses(blue_house_count);
32
        vector<int> red_houses(red_house_count);
33

34
        vector<int> blue_stores(blue_store_count);
35
        vector<int> red_stores(red_store_count);
36

37
        // 파란 집 입력
38
        for (int i = 0; i < blue_house_count; ++i) {
39
            cin >> blue_houses[i];
40
        }
41

42
        // 빨간 집 입력
43
        for (int i = 0; i < red_house_count; ++i) {
44
            cin >> red_houses[i];
45
        }
46

47
        // 파란 상점 입력
48
        for (int i = 0; i < blue_store_count; ++i) {
49
            cin >> blue_stores[i];
50
        }
51

52
        // 빨간 상점 입력
53
        for (int i = 0; i < red_store_count; ++i) {
54
            cin >> red_stores[i];
55
        }
56

57
        ll answer = LLONG_MAX;
58

59
        for (int i = 0; i < 2; ++i) {
60
            // i번째 빨간 상점을 파란 집에 넘긴다
61
            vector<int> current_blue_stores = blue_stores;
62
            current_blue_stores.push_back(red_stores[i]);
63
            sort(current_blue_stores.begin(), current_blue_stores.end());
64

65
            // 남은 빨간 상점은 빨간 집과 매칭
66
            int red_store_for_red = red_stores[1 - i];
67
            int red_house = red_houses[0];
68
            ll red_cost = abs((ll)red_house - red_store_for_red);
69

70
            sort(blue_houses.begin(), blue_houses.end());
71
            ll blue_cost = total_distance(blue_houses, current_blue_stores);
72

73
            answer = min(answer, red_cost + blue_cost);
74
        }
75

76
        // 출력 형식 맞추기
77
        cout << "Case #" << test_case << endl;
78
        cout << answer << endl;
79
    }
80

81
    return 0;
82
}