「一本通 1.1 练习 1」数列极差

题目描述

黑板上写了 $N$ 个正整数。每次操作擦去两个数 $a,b$ ，写入 $a\times b+1$ ，直到只剩一个数。不同操作顺序得到不同结果，最大者记为 $max$ 、最小者记为 $min$ ，求极差 $max-min$ 。输入第一行 $N$ ，第二行 $N$ 个正整数；输出极差。样例输入 3 / 1 2 3，样例输出 2。（原题面未给出 $N$ 的范围。）

思路

每次合并当前最小的两个数能得到最大值，每次合并当前最大的两个数能得到最小值——依据是三个数 $a<b<c$ 的展开式中最晚被合并的那个数单独贡献一项，大数留到最后更大。两个方向各做 $N-1$ 次合并，用小根堆维护最值；求最小方向把数取负放进同一个小根堆即可。复杂度 $O(N\log N)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 09:45
# update_at: 2026-09-30 09:45

import heapq
import sys


def final_value(nums: list[int], pick_smallest: bool) -> int:
    """按题目规则合并到只剩一个数，返回黑板上剩下的那个值。

    pick_smallest 为 True 表示每次取两个最小的数合并（得到最大结果）；
    否则每次取两个最大的数合并（得到最小结果）。实现上把数取负放进
    同一个小根堆，pop 出来的就是原数里最大的两个。
    """
    h = list(nums) if pick_smallest else [-x for x in nums]
    heapq.heapify(h)
    while len(h) > 1:
        x, y = heapq.heappop(h), heapq.heappop(h)
        # 合并规则 a*b+1；取负方向时重新取负放回，保持堆序含义一致
        heapq.heappush(h, x * y + 1 if pick_smallest else -(x * y + 1))
    return h[0] if pick_smallest else -h[0]


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    nums = [next(data) for _ in range(n)]
    print(final_value(nums, True) - final_value(nums, False))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-05 23:26
 * update_at: 2026-10-05 23:26
 */
#include <iostream>
#include <queue>
#include <vector>

using namespace std;

typedef long long ll;

const int MAXN = 100005;

int n;
ll a[MAXN]; // 黑板上最初的 n 个正整数

void read_input() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
}

// 按题目规则每次合并两个数 a、b 为 a*b+1，直到只剩一个数，返回最终值。
// 求 max 时每次合并当前最小的两个数（小根堆）；
// 求 min 时每次合并当前最大的两个数：把数取负放进同一个小根堆，弹出后再还原。
ll merge_all(bool pick_smallest) {
    priority_queue<ll, vector<ll>, greater<ll> > heap;
    for (int i = 0; i < n; i++) {
        if (pick_smallest) {
            heap.push(a[i]);
        } else {
            heap.push(-a[i]);
        }
    }
    while (heap.size() > 1) {
        ll x = heap.top();
        heap.pop();
        ll y = heap.top();
        heap.pop();
        ll merged = x * y + 1;
        if (!pick_smallest) {
            merged = -merged; // 放回堆前再取负，保持"堆顶是原数最大者"
        }
        heap.push(merged);
    }
    ll res = heap.top();
    return pick_smallest ? res : -res;
}

void solve() {
    ll max_value = merge_all(true);
    ll min_value = merge_all(false);
    cout << max_value - min_value << endl;
}

int main() {
    read_input();
    solve();
    return 0;
}

「一本通 1.1 练习 1」数列极差

目录

题目描述

思路

参考代码