ProtyayMnd50 修订了这个 Gist . 跳至此修订
1 file changed, 34 insertions
dem.cpp(file created)
@@ -0,0 +1,34 @@ | |||
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 | + | } |
更新
更早