dem.cpp
· 909 B · C++
Ham
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 | } |