思路与算法

分别求最大最终值和最小最终值。求最大值时，把所有数放入小根堆，每次取最小的两个a、b，插入ab+1；求最小值时使用大根堆，每次取最大的两个。两边各做N−1次合并，最后输出两者之差。因为每次乘积都可能继续参与乘法，数位随输入增长，参考程序使用精确大整数。

正确性说明

令F(a,b)=ab+1。它在正整数域单调，且F(a,b)≥max(a,b)。合并树中的局部交换满足 F(F(a,b),c)−F(a,F(b,c))=c−a；两对分支的重接差为 F(F(a,b),F(c,d))−F(F(a,c),F(b,d))=(d−a)(c−b)。由这两个交换式，可沿两目标叶到公共祖先的路径调整合并树：最大化时把当前最小两个先配成兄弟而不降低根值，最小化时把当前最大两个先配成兄弟而不增加根值。所有外层合并都单调，所以局部改进能传递到整棵树。于是两种极值均存在以对应贪心合并为第一步的最优解；把该兄弟对缩成新数后仍是同类问题，归纳得到两种堆合并的最优性。数值1只会使交换式取等号，不破坏论证。

复杂度

设输入有N个正整数，所有中间整数的最大位数为D。读入与建堆不超过O(N log N·D)；两堆各执行N−1次合并，堆比较O(D)、一次高精度竖式乘法O(D²)，总上界O(N(D²+D log N))。两堆保存O(ND)数位，乘法临时空间O(D)，最终减法O(D)。实际总数位通常比该统一上界小。

易错点

这里不是直接用原序列最大值减最小值；必须把所有合并做完。最大最终值对应先取最小两个，最小最终值对应先取最大两个，方向容易弄反。重复值和1都合法，不能只处理互异或大于1的数。N=1时无须合并，极差为0。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct cpp_int {
    string s;
    bool neg;
    cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
        if (neg)
            s.erase(s.begin());
    }
    void norm() {
        auto p = s.find_first_not_of('0');
        s = p == string::npos ? "0" : s.substr(p);
        if (s == "0")
            neg = false;
    }
    static int cmpabs(const cpp_int &a, const cpp_int &b) {
        if (a.s.size() != b.s.size())
            return a.s.size() < b.s.size() ? -1 : 1;
        return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
    }
    friend bool operator<(const cpp_int &a, const cpp_int &b) {
        if (a.neg != b.neg)
            return a.neg;
        int c = cmpabs(a, b);
        return a.neg ? c > 0 : c < 0;
    }
    friend bool operator==(const cpp_int &a, const cpp_int &b) {
        return a.neg == b.neg && a.s == b.s;
    }
    friend bool operator!=(const cpp_int &a, const cpp_int &b) {
        return !(a == b);
    }
    friend bool operator>(const cpp_int &a, const cpp_int &b) {
        return b < a;
    }
    friend bool operator<=(const cpp_int &a, const cpp_int &b) {
        return !(b < a);
    }
    friend bool operator>=(const cpp_int &a, const cpp_int &b) {
        return !(a < b);
    }
    cpp_int operator-() const {
        cpp_int r = *this;
        if (r.s != "0")
            r.neg = !r.neg;
        return r;
    }
    friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
        cpp_int r;
        r.s.clear();
        int carry = 0;
        if (a.neg == b.neg) {
            int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
            while (i >= 0 || j >= 0 || carry) {
                int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                r.s += char('0' + v % 10);
                carry = v / 10;
            }
            r.neg = a.neg;
        } else {
            const cpp_int *x = &a, *y = &b;
            if (cmpabs(a, b) < 0)
                swap(x, y);
            int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
            while (i >= 0) {
                int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                carry = v < 0;
                if (carry)
                    v += 10;
                r.s += char('0' + v);
            }
            r.neg = x->neg;
        }
        reverse(r.s.begin(), r.s.end());
        r.norm();
        return r;
    }
    friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
        return a + (-b);
    }
    friend cpp_int operator*(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long carry = 0;
        long long z = b;
        if (z < 0)
            z = -z;
        for (int i = (int)a.s.size() - 1; i >= 0; i--) {
            carry += (a.s[i] - '0') * z;
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        while (carry) {
            r.s += char('0' + carry % 10);
            carry /= 10;
        }
        reverse(r.s.begin(), r.s.end());
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    friend cpp_int operator/(const cpp_int &a, int b) {
        cpp_int r;
        r.s.clear();
        long long rem = 0, z = b;
        if (z < 0)
            z = -z;
        for (char c : a.s) {
            rem = rem * 10 + c - '0';
            r.s += char('0' + rem / z);
            rem %= z;
        }
        r.neg = a.neg ^ (b < 0);
        r.norm();
        return r;
    }
    cpp_int &operator+=(const cpp_int &b) {
        *this = *this + b;
        return *this;
    }
    cpp_int &operator-=(const cpp_int &b) {
        *this = *this - b;
        return *this;
    }
    cpp_int &operator*=(int b) {
        *this = *this * b;
        return *this;
    }
    friend istream &operator>>(istream &in, cpp_int &a) {
        string v;
        if (in >> v) {
            a.neg = v[0] == '-';
            if (v[0] == '-' || v[0] == '+')
                v.erase(v.begin());
            a.s = v;
            a.norm();
        }
        return in;
    }
    friend ostream &operator<<(ostream &out, const cpp_int &a) {
        if (a.neg)
            out << '-';
        return out << a.s;
    }
};

cpp_int operator*(const cpp_int &a, const cpp_int &b) {
    vector<long long> v(a.s.size() + b.s.size());
    for (int i = (int)a.s.size() - 1; i >= 0; --i)
        for (int j = (int)b.s.size() - 1; j >= 0; --j)
            v[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
    for (int i = (int)v.size() - 1; i > 0; --i) {
        v[i - 1] += v[i] / 10;
        v[i] %= 10;
    }
    cpp_int c;
    c.s.clear();
    for (auto d : v)
        c.s += char('0' + d);
    c.neg = a.neg != b.neg;
    c.norm();
    return c;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    size_t n;
    cin >> n;
    priority_queue<cpp_int, vector<cpp_int>, greater<cpp_int>> low;
    priority_queue<cpp_int> high;
    for (size_t i = 0; i < n; ++i) {
        cpp_int a;
        cin >> a;
        low.push(a);
        high.push(a);
    }
    while (low.size() > 1) {
        cpp_int a = low.top();
        low.pop();
        cpp_int b = low.top();
        low.pop();
        low.push(a * b + 1);
    }
    while (high.size() > 1) {
        cpp_int a = high.top();
        high.pop();
        cpp_int b = high.top();
        high.pop();
        high.push(a * b + 1);
    }
    cout << low.top() - high.top() << '\n';
}