洛谷 P1090 [NOIP 2004 提高组] 合并果子

// P1090 [NOIP 2004 提高组] 合并果子 —— ★ 这一版就能 AC，而且**不用堆**
//
// 题意：n 堆果子，每次把两堆合并，代价是两堆之和；合并成一堆，求最小总代价。
//
// ★ 贪心是「每次合并**最小的两堆**」（这就是霍夫曼编码的过程）。
//   交换论证的直觉版：一堆果子被合并了几次，它的重量就被数几次 ——
//   所以**越重的堆越要晚合并**。
//
// ★★★ 而这道题挂在第 19 章（排序型贪心）的题单里，是因为它**真的只用排序就能做**：
//   通常的写法是拿[第 37 章的堆](/ch/37-heap/)反复取最小，但这里有一个更省的办法 ——
//
//   **合并产生的新堆，重量是单调不减的。**
//   （每次取走的是当前最小的两堆，它们的和只会越来越大。）
//   ⇒ 于是把「原始堆」排好序放进队列 A，「新产生的堆」按生成顺序放进队列 B，
//     **两个队列都是有序的** —— 每次只要比一下两个队头，谁小取谁。
//   ⇒ 排序 `O(n log n)` ＋ 合并 `O(n)`，一个堆都不用。
//
// ⚠ 题面保证「答案小于 2^31」，也就是说 int 刚好够 —— 但这里仍然写 long long：
//   一是不吃亏，二是「算完确认够用」和「没算过」是两回事。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    sort(a.begin(), a.end());

    queue<long long> A, B;                        // A：原始堆（已排序）　B：合并出来的新堆
    for (int x : a) A.push(x);

    auto take = [&]() {                           // 取当前最小的一堆
        long long x;
        if (B.empty() || (!A.empty() && A.front() <= B.front())) { x = A.front(); A.pop(); }
        else { x = B.front(); B.pop(); }
        return x;
    };

    long long ans = 0;
    for (int i = 1; i < n; i++) {                 // n 堆要合并 n-1 次
        long long x = take(), y = take();
        ans += x + y;
        B.push(x + y);                            // ★ 新堆压到 B 尾部，B 自然还是有序的
    }
    cout << ans << "\n";
    return 0;
}

// P1090 错法：排完序**从头一路累下去**（把新堆直接当成「下一个」）
//
// 写法看着很自然：排好序，先合并最小的两堆，再把结果和第三堆合并，再和第四堆……
// 它的毛病是**新堆没有回到队列里重新排队** —— 而新堆往往不再是最小的那一档了。
//
// ★★ 而官方样例**放过了它**：`1 2 9` 排好之后，
//   `1+2 = 3`，而 3 确实仍然是当时最小的 ⇒ 它和正解走了同一条路，都输出 15。
//   ⇒ 又一次：**样例挡住的是「每组都错」的，放过的是「偶尔才错」的**
//     （这一天四道题都撞上了同一条规律）。
//   最小的反例只要四个 1：正解 `(1+1) (1+1) (2+2)` = 8，这一版 `2, 3, 4` = 9。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n;
    if (!(cin >> n)) return 0;
    vector<long long> a(n);
    for (auto& x : a) cin >> x;
    sort(a.begin(), a.end());

    long long cur = a[0], ans = 0;
    for (int i = 1; i < n; i++) {
        cur += a[i];                              // ← 新堆直接接着往下累，没有重新排队
        ans += cur;
    }
    cout << ans << "\n";
    return 0;
}

// P1090 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1090Count`      人看的版本
// `./p1090Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★★ 验算走一条**和贪心完全无关**的路：答案 ≡ Σ aᵢ × 它在霍夫曼树上的深度；
//   ② ★ 四种正确写法（两队列 / 堆 / 每轮重排 / 每轮线性扫）算出来的是不是同一个数；
//   ③ ★ 那个「一路往下累」的错法的抓获率，以及它的触发条件；
//   ④ ★★★ 第 19 章题单说「先用 sort 硬做也能过」—— 顶格 n = 10⁴ 计时，看这句话对不对；
//   ⑤ ★★ 题面那句「输入数据保证这个值小于 2³¹」是**情报**还是废话 ——
//      算一算顶格数据的答案有多大。

#include <bits/stdc++.h>
#include <chrono>
using namespace std;
using namespace std::chrono;
typedef long long ll;

static bool CSV = false;
static void row(const char* key, const vector<ll>& v) {
    if (!CSV) return;
    printf("%s", key);
    for (ll x : v) printf(",%lld", x);
    printf("\n");
}

/** 正解：两个有序队列（不用堆） */
static ll twoQueues(vector<ll> a) {
    int n = a.size();
    if (n <= 1) return 0;
    sort(a.begin(), a.end());
    queue<ll> A, B;
    for (ll x : a) A.push(x);
    auto take = [&]() {
        ll x;
        if (B.empty() || (!A.empty() && A.front() <= B.front())) { x = A.front(); A.pop(); }
        else { x = B.front(); B.pop(); }
        return x;
    };
    ll ans = 0;
    for (int i = 1; i < n; i++) { ll x = take(), y = take(); ans += x + y; B.push(x + y); }
    return ans;
}
/** 小根堆 */
static ll byHeap(const vector<ll>& a) {
    priority_queue<ll, vector<ll>, greater<ll>> q;
    for (ll x : a) q.push(x);
    ll ans = 0;
    while (q.size() > 1) { ll x = q.top(); q.pop(); ll y = q.top(); q.pop(); ans += x + y; q.push(x + y); }
    return ans;
}
/** 每轮重新 sort */
static ll byResort(vector<ll> a) {
    int n = a.size();
    ll ans = 0;
    for (int step = 1; step < n; step++) {
        sort(a.begin(), a.end());
        ll s = a[0] + a[1];
        ans += s;
        a.erase(a.begin());
        a[0] = s;
    }
    return ans;
}
/** 每轮线性扫两个最小 */
static ll byScan(vector<ll> a) {
    int n = a.size();
    vector<char> gone(n, 0);
    ll ans = 0;
    for (int step = 1; step < n; step++) {
        int i1 = -1, i2 = -1;
        for (int i = 0; i < n; i++) {
            if (gone[i]) continue;
            if (i1 < 0 || a[i] < a[i1]) { i2 = i1; i1 = i; }
            else if (i2 < 0 || a[i] < a[i2]) i2 = i;
        }
        ll s = a[i1] + a[i2];
        ans += s;
        gone[i2] = 1;
        a[i1] = s;
    }
    return ans;
}
/** 错法：排完序一路往下累。touch 记录「有没有出现过『新堆不再是最小』」 */
static ll byChain(vector<ll> a, bool* trig = nullptr) {
    sort(a.begin(), a.end());
    int n = a.size();
    if (trig) *trig = false;
    ll cur = a[0], ans = 0;
    for (int i = 1; i < n; i++) {
        if (trig && i + 1 < n && cur > a[i + 1]) *trig = true;   // 新堆比后面某个原始堆还大
        cur += a[i];
        ans += cur;
    }
    return ans;
}

/** ★ 一条完全无关的路：显式建霍夫曼树，答案 = Σ a_i × depth_i */
static ll byHuffmanDepth(const vector<ll>& a) {
    int n = a.size();
    if (n <= 1) return 0;
    // 结点 0..n-1 是叶子，之后是内部结点
    vector<ll> w(a);
    vector<int> lc, rc;
    lc.assign(n, -1); rc.assign(n, -1);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> q;
    for (int i = 0; i < n; i++) q.push({w[i], i});
    while (q.size() > 1) {
        auto [wx, x] = q.top(); q.pop();
        auto [wy, y] = q.top(); q.pop();
        int id = w.size();
        w.push_back(wx + wy); lc.push_back(x); rc.push_back(y);
        q.push({wx + wy, id});
    }
    int root = w.size() - 1;
    // 算每个叶子的深度，答案 = Σ 叶子权 × 深度
    ll total = 0;
    vector<pair<int, int>> st{{root, 0}};
    while (!st.empty()) {
        auto [u, d] = st.back(); st.pop_back();
        if (lc[u] < 0) { total += w[u] * d; continue; }
        st.push_back({lc[u], d + 1});
        st.push_back({rc[u], d + 1});
    }
    return total;
}

static vector<ll> gen(mt19937& rng, int n, int hi) {
    vector<ll> a(n);
    for (int i = 0; i < n; i++) a[i] = 1 + (ll)(rng() % (unsigned)hi);
    return a;
}

int main(int argc, char** argv) {
    CSV = argc > 1 && string(argv[1]) == "csv";

    /* ① 霍夫曼深度验算 + ② 四种写法一致 */
    {
        mt19937 rng(20260829u);
        int groups = 0, badHuff = 0, badImpl = 0;
        for (int rep = 0; rep < 300; rep++, groups++) {
            int n = (int)(rng() % 40) + 1;
            vector<ll> a = gen(rng, n, 100);
            ll ok = twoQueues(a);
            if (byHuffmanDepth(a) != ok) badHuff++;
            if (byHeap(a) != ok || byResort(a) != ok || byScan(a) != ok) badImpl++;
        }
        if (!CSV) printf("① 验算 %d 组：答案 ≡ Σ a_i × 霍夫曼深度，不同 %d 组\n"
                         "② 四种正确写法（两队列 / 堆 / 每轮重排 / 每轮线性扫）不一致 %d 组\n",
                         groups, badHuff, badImpl);
        row("verify", {groups, badHuff, badImpl});
    }

    /* ③ 「一路往下累」那个错法 */
    {
        const int HIS[] = {2, 20, 2000, 20000};
        vector<ll> out;
        for (int hi : HIS) {
            mt19937 rng(hi * 7919u + 13u);
            int bad = 0, trig = 0, both = 0;
            for (int r = 0; r < 300; r++) {
                int n = (int)(rng() % 12) + 1;
                vector<ll> a = gen(rng, n, hi);
                bool t; ll got = byChain(a, &t);
                bool caught = got != twoQueues(a);
                if (t) trig++;
                if (caught) bad++;
                if (t && caught) both++;
            }
            out.push_back(bad); out.push_back(trig); out.push_back(both);
            if (!CSV) printf("③ a ≤ %5d（n ≤ 12，300 轮）：一路往下累那版错 %d 次；"
                             "「新堆不再是最小」出现 %d 轮，两者同时成立 %d 轮\n", hi, bad, trig, both);
        }
        row("chain", out);
    }

    /* ④ ★★★ 「先用 sort 硬做也能过」—— 顶格 n = 10^4 计时 */
    {
        mt19937 rng(4321u);
        vector<ll> a = gen(rng, 10000, 20000);
        ll ans = twoQueues(a);
        vector<ll> out;
        auto timeit = [&](const char* name, ll (*f)(vector<ll>)) {
            auto t0 = steady_clock::now();
            ll got = f(a);
            ll ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
            if (!CSV) printf("④ %-24s %6lld 毫秒   答案 %lld%s\n", name, ms, got,
                             got == ans ? "" : "  ← 不一致");
            out.push_back(ms);
            return ms;
        };
        timeit("两个有序队列", twoQueues);
        {   // 堆那份的签名是 const&，单独写一次
            auto t0 = steady_clock::now();
            ll got = byHeap(a);
            ll ms = duration_cast<milliseconds>(steady_clock::now() - t0).count();
            if (!CSV) printf("④ %-24s %6lld 毫秒   答案 %lld%s\n", "小根堆（第 37 章）", ms, got,
                             got == ans ? "" : "  ← 不一致");
            out.push_back(ms);
        }
        timeit("每轮线性扫 O(n^2)", byScan);
        timeit("每轮重新 sort O(n^2 log n)", byResort);
        out.push_back(ans);
        row("timing", out);
    }

    /* ⑤ ★★ 题面那句「答案小于 2^31」挡掉了什么 */
    {
        vector<ll> worst(10000, 20000);           // 顶格：10^4 堆，每堆 2×10^4
        ll ans = twoQueues(worst);
        ll total = 0;
        for (ll x : worst) total += x;
        if (!CSV) printf("⑤ 顶格数据（n = 10^4，每堆 2×10^4）：总重 %lld，答案 %lld，"
                         "而 2^31 = 2147483648 —— 答案是它的 %.2f 倍\n",
                         total, ans, (double)ans / 2147483648.0);
        row("worst", {total, ans, 2147483648LL, (ll)((double)ans / 2147483648.0 * 100 + 0.5)});
    }
    return 0;
}

// P1090 对拍生成器：`./p1090Gen <seed> [n 上限] [a 上限]`
//   默认 `n ≤ 12`、`a ≤ 20` —— ★ 故意造得**小而且重复多**。
//
// ★ 理由：这一页那个错法（排完序一路往下累）只在
//   「新合出来的堆不再是当前最小」的时候才现形（最小的反例是四个 1）。
//
// ⚠ 而「值域越小越容易现形」这句话**是我猜的，实测基本不成立**：
//   `a ≤ 2 / 20 / 2000 / 20000` 四档各 300 轮，抓获数是 **210 / 190 / 185 / 188** ——
//   值域拉了一万倍，抓获率几乎没动（页面第 ③ 步那张表）。
//   ⇒ 真正决定它的是 **n**（堆数），不是值域：合的次数多了，
//     「新堆不再是最小」迟早会发生。默认档把 n 压到 12 是为了让暴力参照物跑得动，
//     顺带说明**这个 bug 根本不需要大数据**。

#include <bits/stdc++.h>
using namespace std;

int main(int argc, char** argv) {
    unsigned seed = argc > 1 ? (unsigned)atoi(argv[1]) : 1;
    int nHi = argc > 2 ? atoi(argv[2]) : 12;
    int aHi = argc > 3 ? atoi(argv[3]) : 20;
    nHi = max(1, min(10000, nHi));
    aHi = max(1, min(20000, aHi));

    mt19937 rng(seed * 2654435761u + 90u);
    int n = (int)(rng() % (unsigned)nHi) + 1;
    printf("%d\n", n);
    for (int i = 0; i < n; i++)
        printf("%d%c", 1 + (int)(rng() % (unsigned)aHi), i + 1 == n ? '\n' : ' ');
    return 0;
}