洛谷-P6033 合并果子 加强版（输入输出外挂+基数排序+队列）

题目背景

本题除【数据范围与约定】外与 P1090 完 全 一 致。

题目描述

在一个果园里，多多已经将所有的果子打了下来，而且按果子的不同种类分成了不同的堆。多多决定把所有的果子合成一堆。

每一次合并，多多可以把两堆果子合并到一起，消耗的体力等于两堆果子的重量之和。可以看出，所有的果子经过 (n - 1) 次合并之后， 就只剩下一堆了。多多在合并果子时总共消耗的体力等于每次合并所耗体力之和。

因为还要花大力气把这些果子搬回家，所以多多在合并果子时要尽可能地节省体力。假定每个果子重量都为 1，并且已知果子的种类数和每种果子的数目，你的任务是设计出合并的次序方案，使多多耗费的体力最少，并输出这个最小的体力耗费值。

例如有 3 堆果子，数目依次为 1,2,9。可以先将 1、2 堆合并，新堆数目为 3，耗费体力为 3。接着，将新堆与原先的第三堆合并，又得到新的堆，数目为 12，耗费体力为 12。所以多多总共耗费体力为 3+12=15。可以证明 15为最小的体力耗费值。

输入格式

输入的第一行是一个整数 n，代表果子的堆数。 输入的第二行有 n个用空格隔开的整数，第 i个整数代表第 i堆果子的个数 a_i​。

输出格式

输出一行一个整数，表示最小耗费的体力值。

输入输出样例

输入 #1

3 
1 2 9 

输出 #1

15

说明/提示

【数据规模与约定】

本题采用多测试点捆绑测试，共有四个子任务。

• Subtask 1（10 points）：$1 \leq n \leq 8$。
• Subtask 2（20 points）：$1 \leq n \leq 10^3$。
• Subtask 3（30 points）：$1 \leq n \leq 10^5$。
• Subtask 4（40 points）：$1 \leq n \leq 10^7$。

对于全部的测试点，保证 $1 \leq a_i \leq 10^5$。

【提示】

• 请注意常数因子对程序效率造成的影响。
• 请使用类型合适的变量来存储本题的结果。
• 本题输入规模较大，请注意数据读入对程序效率造成的影响。

---

这道题目是一个很典型，考察的点也比较多，首先在提示部分已经指明了，数据量很大，而且可以根据数据范围知道，结果有可能会超过int范围，所以需要使用long long，同时$10^7$的数据提示我们不能使用优先级队列了，因为时间复杂度是$O(n \log n)$。

不能用优先级队列了，那么还必须对数据排序，因为每次要取出最小的两个，所以需要考虑$O(n)$的排序方法，桶排序，基数排序，计数排序，其中计数排序和桶排序相差无几（在《挑战程序设计竞赛2——数据结构》里认为这两个是同一种算法），在洛谷的题解里面，排名最高的解答指出，虽然本题给出$a_i \leq 10^5$，可以使用桶排序，但是存在卡掉桶排序和计数排序的办法，比如让数据范围$a_i \leq 10^8$，这样就不能开一个$10^8$的数组了，所以使用基数排序是最保险的。

数据排序完成后，这里可以重复利用基数排序的辅助数组tmp，让数组tmp充当队列的作用，用一个head和tail指针模拟队列，每次比较队列头部和数组的元素的大小，选择出最小的两个。因为数组长度为n，最后要只剩下一个元素，那么就需要进行n - 1次。

另外这道题经过尝试，在核心算法不改变的情况下，使用scanf()和关闭同步的cin都会在最后三个测试点超时，所以需要使用快读、快写。（注释的部分也展现了尝试过的输入输出改进办法）

#include <bits/stdc++.h>

using namespace std;

template <typename T>
inline T read()
{
    T res = 0, sign = 1;
    char ch = 0;
    while (!isdigit(ch)) {
        if (ch == '-') sign = -1;
        ch = getchar();
    }

    while (isdigit(ch)) {
        res = res * 10 + (ch - '0');
        ch = getchar();
    }

    return res * sign;
}

template <typename T>
inline void write(T x)
{
    static int myStack[35];
    int top = 0;
    do {
        myStack[top++] = x % 10;
        x /= 10;
    } while (x);

    while (top) putchar(myStack[--top] + '0');
}


int n;
vector<long long> seq(1e7 + 5), tmp(1e7 + 5);
vector<int> countNum(256);

void radixSort()
{
    for (int i = 0; i < 17; i += 8) {
        fill(countNum.begin(), countNum.end(), 0);
        for (int j = 0; j < n; ++j) ++countNum[(seq[j] >> i) & 255];
        for (int j = 1; j < 256; ++j) countNum[j] += countNum[j - 1];
        for (int j = n - 1; j >= 0; --j) tmp[--countNum[(seq[j] >> i) & 255]] = seq[j];
        for (int j = 0; j < n; ++j) seq[j] = tmp[j];
    } 
}

long long solve()
{
    int head = 0, tail = 0;
    int k = 0;
    long long res = 0;
    for (int i = 1; i < n; ++i) {
        long long tmp1, tmp2;
        if (head == tail || (k < n && seq[k] < tmp[head]))
            tmp1 = seq[k++];
        else tmp1 = tmp[head++];

        if (head == tail || (k < n && seq[k] < tmp[head]))
            tmp2 = seq[k++];
        else tmp2 = tmp[head++];

        tmp[tail++] = tmp1 + tmp2;
        res += tmp[tail - 1];
    }

    return res;
}

int main()
{
    // std::ios_base::sync_with_stdio(false);
    // cin.tie(NULL);
    // cout.tie(NULL);

    //cin >> n;
    //scanf("%d", &n);
    n = read<int>();
    for (int i = 0; i < n; ++i) //scanf("%ld", &seq[i]); /* cin >> seq[i]; */
        seq[i] = read<long long>();
    radixSort();
    //cout << solve() << endl;
    write<long long>(solve());

    return 0;
}