本文共 9652 字，大约阅读时间需要 32 分钟。
void heap_adjust(int x){ while(x * 2 <= tot) { int j = x * 2; if(j + 1 <= tot && head[x * 2 + 1] > heap[x * 2]) { j ++; } if(heap[j] > heappx) { swap(heap[x], heap[j]); x = j; } else { break; } }}void Adjust(int tot){ for(int i = tot / 2; i >= 1; i --) { heap_adjust(i); }} #include#include #include void upload_Lb(int k){ while(k > 1) { if(h[k / 2] > h[k]) { swap(h[k / 2], h[k]); k /= 2; } else { return ; } }}void down(int k){ while(2 * k <= tot) { int j = 2 * k; if(j < tot && h[j + 1] < h[j]) { j ++; } if(h[j] < h[k]) { swap(h[j], h[k]); k = j; } else { return ; } }}int main(){ int n; scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%d", h[i]); tot ++; up(tot); } for(int i = 1; i < n; i ++) { tmp = h[1]; h[1] = h[tot--]; down(1); tmp += h[1]; h[1] = h[tot --]; down(1); ans += tmp; h[++ tot] = tmp; up(tot); } printf("%d", ans); return 0;}
代码:
template, class _Pr = less >class priority_queue { public: using value_type = typename _Container::value_type; using reference = typename _Container::reference; using const_reference = typename _Container::const_reference; using size_type = typename _Container::size_type; using container_type = _Container; using value_compare = _Pr; static_assert(is_same_v<_Ty, value_type>, "container adaptors require consistent types"); priority_queue() = default; explicit priority_queue(const _Pr& _Pred) noexcept( is_nothrow_default_constructible_v<_Container>&& is_nothrow_copy_constructible_v ) // strengthened : c(), comp(_Pred) { } priority_queue(const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) { _STD make_heap(c.begin(), c.end(), comp); } priority_queue(const _Pr& _Pred, _Container&& _Cont) : c(_STD move(_Cont)), comp(_Pred) { _STD make_heap(c.begin(), c.end(), comp); } template priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, const _Container& _Cont) : c(_Cont), comp(_Pred) { c.insert(c.end(), _First, _Last); _STD make_heap(c.begin(), c.end(), comp); } template priority_queue(_InIt _First, _InIt _Last) : c(_First, _Last), comp() { _STD make_heap(c.begin(), c.end(), comp); } template priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred) : c(_First, _Last), comp(_Pred) { _STD make_heap(c.begin(), c.end(), comp); } template priority_queue(_InIt _First, _InIt _Last, const _Pr& _Pred, _Container&& _Cont) : c(_STD move(_Cont)), comp(_Pred) { c.insert(c.end(), _First, _Last); _STD make_heap(c.begin(), c.end(), comp); } template , int> = 0> explicit priority_queue(const _Alloc& _Al) noexcept(is_nothrow_constructible_v<_Container, const _Alloc&>&& is_nothrow_default_constructible_v ) // strengthened : c(_Al), comp() { } template , int> = 0> priority_queue(const _Pr& _Pred, const _Alloc& _Al) noexcept(is_nothrow_constructible_v<_Container, const _Alloc&>&& is_nothrow_copy_constructible_v ) // strengthened : c(_Al), comp(_Pred) { } template , int> = 0> priority_queue(const _Pr& _Pred, const _Container& _Cont, const _Alloc& _Al) : c(_Cont, _Al), comp(_Pred) { _STD make_heap(c.begin(), c.end(), comp); } template , int> = 0> priority_queue(const _Pr& _Pred, _Container&& _Cont, const _Alloc& _Al) : c(_STD move(_Cont), _Al), comp(_Pred) { _STD make_heap(c.begin(), c.end(), comp); } template , int> = 0> priority_queue(const priority_queue& _Right, const _Alloc& _Al) : c(_Right.c, _Al), comp(_Right.comp) { } template , int> = 0> priority_queue(priority_queue&& _Right, const _Alloc& _Al) noexcept( is_nothrow_constructible_v<_Container, _Container, const _Alloc&>&& is_nothrow_move_constructible_v ) // strengthened : c(_STD move(_Right.c), _Al), comp(_STD move(_Right.comp)) { } _NODISCARD bool empty() const noexcept(noexcept(c.empty())) /* strengthened */ { return c.empty(); } _NODISCARD size_type size() const noexcept(noexcept(c.size())) /* strengthened */ { return c.size(); } _NODISCARD const_reference top() const noexcept(noexcept(c.front())) /* strengthened */ { return c.front(); } void push(const value_type& _Val) { c.push_back(_Val); _STD push_heap(c.begin(), c.end(), comp); } void push(value_type&& _Val) { c.push_back(_STD move(_Val)); _STD push_heap(c.begin(), c.end(), comp); } template void emplace(_Valty&&... _Val) { c.emplace_back(_STD forward<_Valty>(_Val)...); _STD push_heap(c.begin(), c.end(), comp); } void pop() { _STD pop_heap(c.begin(), c.end(), comp); c.pop_back(); } void swap(priority_queue& _Right) noexcept( _Is_nothrow_swappable<_Container>::value&& _Is_nothrow_swappable<_Pr>::value) { _Swap_adl(c, _Right.c); _Swap_adl(comp, _Right.comp); }protected: _Container c{ }; _Pr comp{ };};#if _HAS_CXX17template >, negation<_Is_allocator<_Container>>>, int> = 0>priority_queue(_Pr, _Container) -> priority_queue ;template >, class _Container = vector<_Iter_value_t<_Iter>>, enable_if_t <_Is_iterator<_Iter>, negation<_Is_allocator<_Pr>>, negation<_Is_allocator<_Container>>>, int> = 0>priority_queue(_Iter, _Iter, _Pr = _Pr(), _Container = _Container()) -> priority_queue<_Iter_value_t<_Iter>, _Container, _Pr>;template >, negation<_Is_allocator<_Container>>, _Is_allocator<_Alloc>, uses_allocator<_Container, _Alloc>>, int> = 0>priority_queue(_Pr, _Container, _Alloc) -> priority_queue ;#endif // _HAS_CXX17template ::value && _Is_swappable<_Pr>::value, int> = 0>void swap(priority_queue<_Ty, _Container, _Pr>& _Left, priority_queue<_Ty, _Container, _Pr>& _Right) noexcept( noexcept(_Left.swap(_Right))) { _Left.swap(_Right);}
1
#include#include #include using namespace std;int main(){ priority_queue q; // 可以是任意的类型 long long ret = 0; int n; scanf("%d", &n); int x; for(int i = 1; i <= n; i ++) { scanf("%d", &x); q.push(-x); } while(q.size() > 1) { long long a = -q.top(); q.pop(); long long b = -q.top(); q.pop(); ret += a + b; q.push(-a - b); } printf("%lld", ret); return 0;}
2
#include#include #include using namespace std;int n;priority_queue , greater > q;int main(){ long long x, y, sum = 0LL; scanf("%d", &n); for(int i = 1; i <= n; i ++) { scanf("%lld", &x); q.push(x); } for(int i = 1; i < n; i ++) { x = q.top(); q.pop(); y = q.top(); q.pop(); sum += x + y; q.push(x + y); } printf("%lld\n", sum); return 0;}
3
#include#include #include using namespace std;struct node{ long long v; bool operator < (const struct node x) const { return v > x.v; // ^_^ }}cur;priority_queue pq;int main(){ int n; long long sum = 0; scanf("%d", &n); for(int i = 0; i < n; i ++) { scanf("%lld", &cur.v); pq.push(cur); } for(int i = 1; i < n; i ++) { cur = pq.top(); pq.pop(); cur.v += pq.top().v; pq.pop(); sum += cur.v; pq.push(cur); } printf("%lld\n", sum); return 0;}
#include#include using namespace std; void max_heapify(int arr[], int start, int end) { //建立父节点指标和子节点指标 int dad = start; int son = dad * 2 + 1; while (son <= end) //若子节点指标在范围内才做比较 { if (son + 1 <= end && arr[son] < arr[son + 1]) //先比较两个子节点大小，选择最大的 son++; if (arr[dad] > arr[son]) //如果父节点大於子节点代表调整完毕，直接跳出函数 return; else //否则交换父子内容再继续子节点和孙节点比较 { swap(arr[dad], arr[son]); dad = son; son = dad * 2 + 1; } }} void heap_sort(int arr[], int len) { //初始化，i从最後一个父节点开始调整 for (int i = len / 2 - 1; i >= 0; i--) max_heapify(arr, i, len - 1); //先将第一个元素和已经排好的元素前一位做交换，再从新调整(刚调整的元素之前的元素)，直到排序完毕 for (int i = len - 1; i > 0; i--) { swap(arr[0], arr[i]); max_heapify(arr, 0, i - 1); }} void main() { int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 }; int len = (int) sizeof(arr) / sizeof(*arr); heap_sort(arr, len); for (int i = 0; i < len; i++) cout << arr[i] << ' '; cout << endl; system("pause"); return 0;}
You got a dream, you gotta protect it. People can’t do something themselves, they wanna tell you you can’t do it. If you want something, go get it. Period.
转载地址：http://yfsyk.baihongyu.com/