网站建设 教程,南京太阳宫网站建设,vue框架做的网站,南昌做网站软件目录 题目描述
解题思路
代码部分 题目描述
在黑板上写了N个正整数作成的一个数列#xff0c;进行如下操作#xff1a;每一次擦去其中的两个数a和b#xff0c;然后在数列中加入一个数a*b1#xff0c;如此下去直至黑板上剩下一个数#xff0c;在所有按这种操作方式最后得…目录 题目描述
解题思路
代码部分 题目描述
在黑板上写了N个正整数作成的一个数列进行如下操作每一次擦去其中的两个数a和b然后在数列中加入一个数a*b1如此下去直至黑板上剩下一个数在所有按这种操作方式最后得到的数中最大的max最小的为min则该数列的极差定义为Mmax-min。
输入
第一行一个数为N;
第二行N个数。
输出
输出极差。
样例输入
3
1 2 3
样例输出
2
解题思路
经过计算可以证明
当输入的一行数按升序排列时最终算出的结果值最大
当输入的一行数按降序排列时最终算出的结果值最小。解题关键
可以采用优先队列解题最终队列剩下的那个值就是这一行数最终算出来的结果。
升序和降序队列的计算可以双线同时进行。
升序优先队列的解决方法
默认的优先队列是降序排列的优先队列如何能让降序队列变成升序队列呢有一个简单方法
将降序队列的所有数变成原来的相反数再用“优先队列”存储得到的队列和原队列正好相反
原来的队列是降序队列现在的队列就成功转化成了升序队列
转化成升序队列之后一定要时刻注意不能直接调用升序队列存储的数据因为升序队列存储的数据是原数据的相反数。同时继续向升序队列队尾push值的时候一定要先变成相反数再推入
代码部分
#include iostream
#include cstring
#include queue
typedef long long ll;
using namespace std;
priority_queuelldown;//降序
priority_queuellup;//升序
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*y1)!!!}cout -up.top() - down.top();//up.top()是原本数据的相反数最后这里也要变回来return 0;
}
