1555数列极差（队列 优先队列 ）

目录

题目描述

解题思路

代码部分

---

题目描述

在黑板上写了N个正整数作成的一个数列，进行如下操作：每一次擦去其中的两个数a和b，然后在数列中加入一个数a*b+1，如此下去直至黑板上剩下一个数，在所有按这种操作方式最后得到的数中，最大的max，最小的为min，则该数列的极差定义为M=max-min。

输入

第一行，一个数为N;

第二行，N个数。

输出

输出极差。

样例输入

3
1 2 3

样例输出

2

解题思路

经过计算可以证明：

当输入的一行数按升序排列时，最终算出的结果值最大；

当输入的一行数按降序排列时，最终算出的结果值最小。（解题关键）

可以采用优先队列解题，最终队列剩下的那个值就是这一行数最终算出来的结果。

升序和降序队列的计算可以双线同时进行。

升序优先队列的解决方法：

默认的优先队列是降序排列的优先队列，如何能让降序队列变成升序队列呢？有一个简单方法：

将降序队列的所有数变成原来的相反数，再用“优先队列”存储，得到的队列和原队列正好相反，

原来的队列是降序队列，现在的队列就成功转化成了升序队列！

转化成升序队列之后一定要时刻注意，不能直接调用升序队列存储的数据！因为升序队列存储的数据是原数据的相反数。同时，继续向升序队列队尾push值的时候，一定要先变成相反数再推入！！

代码部分

#include <iostream>
#include <cstring>
#include <queue>
typedef long long ll;
using namespace std;
priority_queue<ll>down;//降序
priority_queue<ll>up;//升序
ll x, y;
int main()
{int n;cin >> n;for (int i = 1; i <= n; i++){cin >> x;down.push(x);//降序up.push(-x);//升序。//默认的优先队列按照降序存储，//所以如果想要实现升序存储，只能存入-x;}for (int i = 1; i < n; i++){//处理降序队列的问题x = down.top(); down.pop();y = down.top(); down.pop();down.push(x * y + 1);//处理升序队列的问题x = -up.top(); up.pop();//因为在实现升序存储时将存入的数据变成了相反数，//所以这里调用真实数据时必须再取一次相反数y = -up.top(); up.pop();up.push(-(x * y + 1));//x*y=(-x)*(-y)//这里一定要注意!!!//别忘了实现升序排列要将数据变成相反数存储!!!//一定是-(x*y+1)!!!}cout << -up.top() - down.top();//up.top()是原本数据的相反数，最后这里也要变回来return 0;
}