优先队列——数列极差

Day7：数列极差

优先队列保证每次取出的元素都是当前优先级最高的元素。其底层实现通常是堆（Heap），因此插入和删除的时间复杂度都是O(logN)，访问队首元素的时间复杂度是O(1)。

a.push()    插入元素
a.top()    访问队首元素
a.pop()    弹出队首元素

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    int n;
    cin >> n;
    vector<ll> a(n);
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }


    priority_queue<ll, vector<ll>, greater<ll>> qwe;
    for(ll x : a) qwe.push(x);
    while(qwe.size() > 1) {
        ll x = qwe.top(); qwe.pop();
        ll y = qwe.top(); qwe.pop();
        qwe.push(x * y + 1);
    }
    ll minn = qwe.top();


    priority_queue<ll> asd;
    for(ll x : a) asd.push(x);
    while(asd.size() > 1) {
        ll x = asd.top(); asd.pop();
       ll y = asd.top(); asd.pop();
        asd.push(x * y + 1);
    }
    ll maxx = asd.top();

    cout <<abs(maxx - minn)<< endl;
    return 0;
}