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 class Solution {public : long long totalCost (vector<int >& costs, int k, int candidates) { int n = costs.size (); priority_queue<pair<int , int >, vector<pair<int , int >>, greater<pair<int , int >>> q; int left = candidates - 1 , right = n - candidates; if (left + 1 < right) { for (int i = 0 ; i <= left; ++i) { q.emplace (costs[i], i); } for (int i = right; i < n; ++i) { q.emplace (costs[i], i); } } else { for (int i = 0 ; i < n; ++i) { q.emplace (costs[i], i); } } long long ans = 0 ; for (int _ = 0 ; _ < k; ++_) { auto [cost, id] = q.top (); q.pop (); ans += cost; if (left + 1 < right) { if (id <= left) { ++left; q.emplace (costs[left], left); } else { --right; q.emplace (costs[right], right); } } } return ans; } };
要找到最小的总代价,只涉及简单的比较而不需要做决策,显然这是一个排序问题。
由于只需要排序前candidates位和后candidates位工人的代价,这是一个堆排序问题,要找到最小值,使用小顶堆。
C++中使用优先队列priority_queue
实现堆排序,代码如上。
优先队列
定义:priority_queue<Type, Container, Functional>
Type 就是数据类型,Container
就是容器类型(Container必须是用数组实现的容器,比如vector,deque等等,但不能用
list。STL里面默认用的是vector),Functional
就是比较的方式,当需要用自定义的数据类型时才需要传入这三个参数,使用基本数据类型时,只需要传入数据类型,默认是大顶堆
1 2 3 4 5 6 priority_queue <int ,vector<int >,greater<int > > q; priority_queue <int ,vector<int >,less<int > >q;
优先队列是用堆实现的,它使得队列内部的元素具有优先级,改变出队顺序。因此优先队列具有队列的所有特性,包括基本操作:
和队列基本操作相同:
top 访问队头元素
empty 队列是否为空
size 返回队列内元素个数
push 插入元素到队尾 (并排序)
emplace 原地构造一个元素并插入队列
pop 弹出队头元素
swap 交换内容