题目描述

【数列极差】问题描述：在黑板上写了 $N$ 个正整数组成的一个数列，进行如下操作：每一次擦去其中的两个数 $a$ 和 $b$， 然后在数列中加入一个数 $a*b+1$，如此下去直至黑板上剩下一个数，在所有按这种操作方式得到的所有数中，最大的 $\max$，最小的为 $\min$，则该数列的极差定义为 $M = \max - \min$。试设计一个算法，计算 $M$。

【 Sequence Extreme Difference 】 Problem Description: A sequence composed of $N$ positive integers is written on the blackboard. The following operation is performed: erase two numbers $a$ and $b$, then add a number $a*b+1$ to the sequence. Repeat this process until only one number remains on the blackboard. Among all the numbers obtained by this operation, let the maximum be $\max$ and
the minimum be $\min$. The extreme difference $M$ of the sequence is defined as $M = \max - \min$. Design an algorithm to calculate $M$.

样例

3
1 2 3

算法1

(暴力枚举) $O(n!^2)$

遍历每一个可能的选择，

复杂度

• 时间复杂度 $O(n!^2)$ 不可思议
• 空间复杂度 $O(n!)$

C++ 代码

//
// Created by tianq on 24-12-9.
//
// This is a stupid brute-forced implementation, but it must work
// it takes 135786 calculations for 7 inputs LOL, the time & space complexity is VERY BAD
// time: $O(n!^2)$, space: $O(n!)$
// hint: n=9: 136873332calc(5min), 57153600vectors(2340mb), problem size must be 8 or less
//
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;
    vector<int> numbers;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        numbers.push_back(tmp);
    }

    // brute force version: try every possible combinations, until only one left
    // we are not bundling a problem generator here
    unsigned long long calc = 0;
    unsigned long long memMax = 0;
    vector<int> results;
    queue<vector<int>> q;
    q.push(numbers);

    while (!q.empty()) {
        memMax = max(memMax, q.size());

        vector<int> v = q.front();
        q.pop();

        if (v.size() < 2) {
            results.push_back(v.front());
            // cout << v.front() << endl;
            continue;
        }

        // choose 2 numbers from v and push new task to q
        for (int i = 0; i < v.size() - 1; i++) {
            for (int j = i + 1; j < v.size(); j++) {
                const int a = v[i];
                const int b = v[j];
                const int res = a * b + 1;
                calc ++;
                vector<int> tv = v;
                tv.erase(tv.begin() + j);
                tv.erase(tv.begin() + i);
                tv.emplace_back(res);
                q.push(tv);
            }
        }
    }

    const int max = ranges::max(results);
    const int min = ranges::min(results);
    cout << "calc: " << calc << ", memMax: " << memMax << " vectors" << endl;
    cout << "max: " << max << ", min: " << min << endl;
    cout << "M: " << max - min << endl;
    return 0;
}

算法2

(贪心) $O(n \log n)$

很显然，这道题不能暴力求解，我们需要一点注意到

• 每次选取两个最小的数合并，最终结果最大
• 每次选取两个最大的数合并，最终结果最小

复杂度

• 时间复杂度 $O(n \log n)$
• 空间复杂度 $O(n)$

C++ 代码

//
// Created by tianq on 24-12-9.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;
    vector<int> numbers;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        numbers.emplace_back(tmp);
    }

    // ideology
    // by merging smallest 2 each time, we get the biggest one
    // by merging greatest 2 each time, we get the smallest one
    // don't just take my words, try it on paper

    vector<int> maxNums = numbers, minNums = numbers;

    ranges::sort(maxNums);
    while (maxNums.size() > 1) {
        int newNum = maxNums[0] * maxNums[1] + 1;
        maxNums.erase(maxNums.begin(), maxNums.begin() + 2);
        // since our vector is already ordered, we don't need to sort again
        auto it = ranges::lower_bound(maxNums, newNum);
        maxNums.emplace(it, newNum);
    }

    ranges::sort(minNums, greater());
    while (minNums.size() > 1) {
        int newNum = minNums[0] * minNums[1] + 1;
        minNums.erase(minNums.begin(), minNums.begin()+2);
        // the product of two biggest numbers should still be biggest 
        minNums.emplace(minNums.begin(), newNum);
    }

    cout << maxNums[0] - minNums[0] << endl;
}

上面的代码要求C20，acwing的oj目前不认，可以尝试下面的代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n = 0;
    vector<int> numbers;

    cin >> n;
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        numbers.emplace_back(tmp);
    }

    // ideology
    // by merging smallest 2 each time, we get the biggest one
    // by merging greatest 2 each time, we get the smallest one
    // don't just take my words, try it on paper

    vector<int> maxNums = numbers, minNums = numbers;

    sort(maxNums.begin(), maxNums.end());
    while (maxNums.size() > 1) {
        int newNum = maxNums[0] * maxNums[1] + 1;
        maxNums.erase(maxNums.begin(), maxNums.begin() + 2);
        auto it = lower_bound(maxNums.begin(), maxNums.end(), newNum);
        maxNums.emplace(it, newNum);
    }

    sort(minNums.begin(), minNums.end(), greater());
    while (minNums.size() > 1) {
        int newNum = minNums[0] * minNums[1] + 1;
        minNums.erase(minNums.begin(), minNums.begin()+2);
        minNums.emplace(minNums.begin(), newNum);
    }

    cout << maxNums[0] - minNums[0] << endl;
}