「贪心&优先队列」数列极差

本题为12月30日22寒假集训每日一题题解

题目来源:(未知)

题面

题目描述

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

由于佳佳忙于准备期末考试，现请你帮助他，对于给定的数列，计算出相应的极差M。

输入

第一行为一个正整数n表示正整数序列的长度；

在接下来的n行中，每行输入一个正整数。

接下来的一行有一个0，表示数据结束。

输出

输出只有一行，为相应的极差d。

样例输入

3
1
2
3
0

样例输出

2

提示

对于全部数据，0≤n≤50000，保证所有数据计算均在32位有符号整数范围内。

思路分析

凭直觉想到的贪心策略,目前还没看懂证明,日后再补.

参考代码

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3, "Ofast", "inline")

#include <iostream>
#include <queue>

using namespace std;
 
int main()
{
    ios::sync_with_stdio(false);
 
    int n;
    cin >> n;
 
    if (n <= 1)
    {
        cout << 0 << "\n";
        return 0;
    }
 
    priority_queue<int> a;
    priority_queue<int, vector<int>, greater<int>> b;
 
    for (int i = 0; i < n; i++)
    {
        int num;
        cin >> num;
        a.push(num);
        b.push(num);
    }
 
    int max, min;
 
    while (a.size() > 1)
    {
        int num = a.top();
        a.pop();
        num = num * a.top() + 1;
        a.pop();
        a.push(num);
    }
 
    while (b.size() > 1)
    {
        int num = b.top();
        b.pop();
        num = num * b.top() + 1;
        b.pop();
        b.push(num);
    }
 
    min = a.top();
    max = b.top();
 
    cout << max - min << "\n";
    return 0;
}

"正是我们每天反复做的事情，最终造就了我们，优秀不是一种行为，而是一种习惯" ---亚里士多德