dem.cpp
· 909 B · C++
Eredeti
int N = segments.size();
vector<vector<int>> sortedSegments = segments;
sort(sortedSegments.begin(), sortedSegments.end(), [](const vector<int> &a, const vector<int> &b) {
return a[1] < b[1];
});
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap;
int min_cost = numeric_limits<int>::max();
for (const auto &segment : sortedSegments) {
int L = segment[0];
int R = segment[1];
int cost = segment[2];
while (!minHeap.empty() && minHeap.top().first >= L) {
minHeap.pop();
}
if (!minHeap.empty()) {
int pairing_cost = minHeap.top().second * cost;
min_cost = min(min_cost, pairing_cost);
}
minHeap.push({R, cost});
}
return (min_cost != numeric_limits<int>::max()) ? min_cost : -1;
}
1 | int N = segments.size(); |
2 | |
3 | |
4 | vector<vector<int>> sortedSegments = segments; |
5 | sort(sortedSegments.begin(), sortedSegments.end(), [](const vector<int> &a, const vector<int> &b) { |
6 | return a[1] < b[1]; |
7 | }); |
8 | |
9 | |
10 | priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> minHeap; |
11 | int min_cost = numeric_limits<int>::max(); |
12 | |
13 | for (const auto &segment : sortedSegments) { |
14 | int L = segment[0]; |
15 | int R = segment[1]; |
16 | int cost = segment[2]; |
17 | |
18 | |
19 | while (!minHeap.empty() && minHeap.top().first >= L) { |
20 | minHeap.pop(); |
21 | } |
22 | |
23 | |
24 | if (!minHeap.empty()) { |
25 | int pairing_cost = minHeap.top().second * cost; |
26 | min_cost = min(min_cost, pairing_cost); |
27 | } |
28 | |
29 | |
30 | minHeap.push({R, cost}); |
31 | } |
32 | |
33 | return (min_cost != numeric_limits<int>::max()) ? min_cost : -1; |
34 | } |