数列极差

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1048 字

小顶堆求最大、大顶堆求最小后相减

一本通
练习

正文

// 原题：https://oj.yecheng.tv/p/T1427
// 题意：N 个正整数，每次擦掉两个数 a、b 并加入 a * b + 1，直到只剩一个数，求所有操作顺序下最大值与最小值的差。
// 思路：两个方向各做一次贪心。
// 1. 求最大值：每次取最小的两个数合并（小顶堆）。
// 2. 求最小值：每次取最大的两个数合并（大顶堆）。
// 3. 答案为两次结果的差。
// 复杂度：O(n log n) 时间 / O(n) 空间
// 易错点：合并公式是 a * b + 1，合并后还要把新数放回堆里继续参与运算。
// 易错点：数列元素可能较大，累乘结果要用 long long，避免中间结果溢出。
#include <bits/stdc++.h>
using namespace std;
int main(){
    int n;
    if(!(cin >> n)) return 0;
    priority_queue<long long, vector<long long>, greater<long long>> small;
    priority_queue<long long> big;
    for(int i = 0; i < n; i++){
        long long x;
        cin >> x;
        small.push(x);
        big.push(x);
    }
    while(small.size() > 1){
        long long a = small.top();
        small.pop();
        long long b = small.top();
        small.pop();
        small.push(a * b + 1);
    }
    while(big.size() > 1){
        long long a = big.top();
        big.pop();
        long long b = big.top();
        big.pop();
        big.push(a * b + 1);
    }
    cout << small.top() - big.top() << "\n";
    return 0;
}

数列极差

正文

一本通·提高篇的其它内容