目錄

題目描述

解題思路

代碼部分

---

題目描述

在黑板上寫了N個(gè)正整數(shù)作成的一個(gè)數(shù)列，進(jìn)行如下操作：每一次擦去其中的兩個(gè)數(shù)a和b，然后在數(shù)列中加入一個(gè)數(shù)a*b+1，如此下去直至黑板上剩下一個(gè)數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的max，最小的為min，則該數(shù)列的極差定義為M=max-min。

輸入

第一行，一個(gè)數(shù)為N;

第二行，N個(gè)數(shù)。

輸出

輸出極差。

樣例輸入

3
1 2 3

樣例輸出

2

解題思路

經(jīng)過(guò)計(jì)算可以證明：

當(dāng)輸入的一行數(shù)按升序排列時(shí)，最終算出的結(jié)果值最大；

當(dāng)輸入的一行數(shù)按降序排列時(shí)，最終算出的結(jié)果值最小。（解題關(guān)鍵）

可以采用優(yōu)先隊(duì)列解題，最終隊(duì)列剩下的那個(gè)值就是這一行數(shù)最終算出來(lái)的結(jié)果。

升序和降序隊(duì)列的計(jì)算可以雙線同時(shí)進(jìn)行。

升序優(yōu)先隊(duì)列的解決方法：

默認(rèn)的優(yōu)先隊(duì)列是降序排列的優(yōu)先隊(duì)列，如何能讓降序隊(duì)列變成升序隊(duì)列呢？有一個(gè)簡(jiǎn)單方法：

將降序隊(duì)列的所有數(shù)變成原來(lái)的相反數(shù)，再用“優(yōu)先隊(duì)列”存儲(chǔ)，得到的隊(duì)列和原隊(duì)列正好相反，

原來(lái)的隊(duì)列是降序隊(duì)列，現(xiàn)在的隊(duì)列就成功轉(zhuǎn)化成了升序隊(duì)列！

轉(zhuǎn)化成升序隊(duì)列之后一定要時(shí)刻注意，不能直接調(diào)用升序隊(duì)列存儲(chǔ)的數(shù)據(jù)！因?yàn)樯蜿?duì)列存儲(chǔ)的數(shù)據(jù)是原數(shù)據(jù)的相反數(shù)。同時(shí)，繼續(xù)向升序隊(duì)列隊(duì)尾push值的時(shí)候，一定要先變成相反數(shù)再推入！！

代碼部分

#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);//升序。//默認(rèn)的優(yōu)先隊(duì)列按照降序存儲(chǔ)，//所以如果想要實(shí)現(xiàn)升序存儲(chǔ)，只能存入-x;}for (int i = 1; i < n; i++){//處理降序隊(duì)列的問(wèn)題x = down.top(); down.pop();y = down.top(); down.pop();down.push(x * y + 1);//處理升序隊(duì)列的問(wèn)題x = -up.top(); up.pop();//因?yàn)樵趯?shí)現(xiàn)升序存儲(chǔ)時(shí)將存入的數(shù)據(jù)變成了相反數(shù)，//所以這里調(diào)用真實(shí)數(shù)據(jù)時(shí)必須再取一次相反數(shù)y = -up.top(); up.pop();up.push(-(x * y + 1));//x*y=(-x)*(-y)//這里一定要注意!!!//別忘了實(shí)現(xiàn)升序排列要將數(shù)據(jù)變成相反數(shù)存儲(chǔ)!!!//一定是-(x*y+1)!!!}cout << -up.top() - down.top();//up.top()是原本數(shù)據(jù)的相反數(shù)，最后這里也要變回來(lái)return 0;
}