第一条题解

注意到最大值策略是每次取2个最小 最小值策略是每次取2个最大
如果用sort维持大小关系，则单次O(n log n)一共2n次时间复杂度为O(n*n log n)对于这题会超时
因此我们用堆
一个大根堆，一个小根堆，一个中根堆

#include<bits/stdc++.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    priority_queue<int, vector<int>, greater<int>> a;
    priority_queue<int, vector<int>, less<int>> b;
    for(int i=1; i<=n; i++){
        int x;
        cin>>x;
        a.push(x);
        b.push(x);
    }
    int maxn=0,minn=0;
    while(a.size()>1){
        int x=a.top();
        a.pop();
        int y=a.top();
        a.pop();
        a.push(x*y+1);
    }
    while(b.size()>1){
        int x=b.top();
        b.pop();
        int y=b.top();
        b.pop();
        b.push(x*y+1);
    }
    cout<<a.top()-b.top();


    return 0;
}