DSA/first.cpp at main · shrihari7396/DSA · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
// #include <iostream>
// #include <vector>
// #include <algorithm>
// using namespace std;

// struct House {
//     int num;
//     int pos;
// };

// bool cmp(const House &a, const House &b) {
//     return a.pos < b.pos;
// }

// int main() {
//     int n, val;
//     cin >> n >> val;
//     vector<House> houses(n);
//     for (int i = 0; i < n; ++i) {
//         cin >> houses[i].num >> houses[i].pos;
//     }
//     sort(houses.begin(), houses.end(), cmp);

//     int max_dist = -1;
//     int ref = 1e9;
//     int h1 = 0, h2 = 0;
//     for (int i = 1; i < n; ++i) {
//         int dist = houses[i].pos - houses[i-1].pos;
//         int num1 = min(houses[i].num, houses[i-1].num);
//         int num2 = max(houses[i].num, houses[i-1].num);
//         int local_ref = min(num1, num2);
//         if (dist > max_dist ||
//            (dist == max_dist && local_ref < ref)) {
//             max_dist = dist;
//             h1 = num1;
//             h2 = num2;
//             ref = local_ref;
//         }
//     }
//     cout << h1 << " " << h2 << endl;
//     return 0;
// }

#include <iostream>
#include <vector>
#include <climits>
#include <cmath>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;

    vector<int> systemState(n);
    for (int i = 0; i < n; i++) {
        cin >> systemState[i];
    }

    vector<long long> dist(n);
    for (int i = 0; i < n; i++) {
        cin >> dist[i];
    }

    vector<long long> onPositions;

    // Collect ON system positions
    for (int i = 0; i < n; i++) {
        if (systemState[i] == 1) {
            onPositions.push_back(dist[i]);
        }
    }

    // Sort ON positions for binary search
    sort(onPositions.begin(), onPositions.end());

    long long totalCable = 0;

    // For each OFF system, find nearest ON system using binary search
    for (int i = 0; i < n; i++) {
        if (systemState[i] == 0) {
            long long pos = dist[i];

            // Binary search for closest ON system
            auto it = lower_bound(onPositions.begin(), onPositions.end(), pos);

            long long minDist = LLONG_MAX;

            // Check the closest positions
            if (it != onPositions.end()) {
                minDist = min(minDist, abs(pos - *it));
            }
            if (it != onPositions.begin()) {
                --it;
                minDist = min(minDist, abs(pos - *it));
            }

            totalCable += minDist;
        }
    }

    cout << totalCable << endl;
    return 0;
}