洛谷 P1094 [NOIP 2007 普及组] 纪念品分组

// P1094 [NOIP 2007 普及组] 纪念品分组 —— ★ 这一版就能 AC
//
// 题意：n 件纪念品，价格 P_i；**每组最多两件**，每组价格之和 ≤ w，求最少分几组。
//
// ★ 关键一步：排序之后用[第 7 章的对撞双指针](/ch/07-two-pointers/)，
//   **最贵的那件去配最便宜的那件**：配得上就成一组，配不上就让它自己单独一组。
//
// 交换论证（比排队接水那次绕一点）：设最贵的是 X。
//   · 如果最便宜的 Y 都配不上 X（`X + Y > w`），那**谁都配不上 X** ⇒ X 只能单独一组；
//   · 如果配得上，那么让 X 配 Y **不吃亏**：假设最优解里 X 配的是 Z、Y 配的是 U，
//     把它们换成 (X, Y) 和 (Z, U) —— `Z + U ≤ X + Z ≤ w`（因为 Y 最小、X 最大），
//     ⇒ 换完仍然合法，组数一个没多。
//   ⇒ 所以「最贵配最便宜」一定能达到最优。
//
// ⚠ 三处容易栽的地方（页面上各量了一个）：
//   ① 输入格式是 **w 在第一行、n 在第二行**（比常见的「先 n 后 w」反过来）；
//   ② 循环条件是 `l <= r` 不是 `l < r` —— 剩下最后一件时它也要自己成一组；
//   ③ ★★★ 一个**看起来更聪明**的贪心（每组尽量填满 w，也就是装箱里的 best-fit）
//      在这道题上是**错的**，而它错得很轻 —— 页面第 ④ 步量了它。
//
// 复杂度 O(n log n)，全花在排序上（★ 而 P_i ≤ 200，桶排能做到 O(n + w)）。

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

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

    int l = 0, r = n - 1, cnt = 0;
    while (l <= r) {                              // ★ 是 <=
        if (a[l] + a[r] <= w) l++;                // 最便宜的能搭上最贵的，一起走
        r--;                                      // 最贵的这件无论如何都走
        cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

// P1094 的参照物：**枚举所有分组方案**（不排序、不贪心）
//
// ★ 这道题的三个错法都只差一两行，而且每一个都「听起来有道理」——
//   所以参照物必须彻底离开贪心这条路。
//
// 造法：递归。取还没分组的第一件，它要么**自己单独一组**，
//   要么和后面某一件配成一组（前提是和 ≤ w）。取所有分支里组数最少的。
//   复杂度大约 O(n!!)，只跑得动 n ≤ 12 —— 但它**不需要任何想法**，这正是它的价值。

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

static int n, w, best;
static vector<int> a;
static vector<char> used;

static void dfs(int done, int groups) {
    if (groups >= best) return;                   // 已经不可能更好
    if (done == n) { best = min(best, groups); return; }
    int i = 0;
    while (i < n && used[i]) i++;                 // 第一件还没分组的
    used[i] = 1;
    dfs(done + 1, groups + 1);                    // ① 它自己一组
    for (int j = i + 1; j < n; j++) {             // ② 和后面某一件配
        if (used[j] || a[i] + a[j] > w) continue;
        used[j] = 1;
        dfs(done + 2, groups + 1);
        used[j] = 0;
    }
    used[i] = 0;
}

int main() {
    if (!(cin >> w >> n)) return 0;
    a.assign(n, 0);
    for (int& x : a) cin >> x;
    used.assign(n, 0);
    best = n + 1;
    dfs(0, 0);
    cout << best << "\n";
    return 0;
}

// P1094 错法一：循环条件写成 `l < r`
//
// 剩下最后一件（`l == r`）时，它也**必须自己占一组** —— 而 `l < r` 直接把它漏掉了。
//
// ★ 它什么时候现形？**只在「最后剩奇数个」的时候** —— 页面第 ④ 步量了它的抓获率。

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

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

    int l = 0, r = n - 1, cnt = 0;
    while (l < r) {                               // ← 这里
        if (a[l] + a[r] <= w) l++;
        r--;
        cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

// P1094 错法二：排完序**相邻两两配**
//
// 「排好序，一二一起、三四一起」是很常见的第一反应 ——
// 它把「最贵的配最便宜的」听成了「差不多贵的配在一起」。
//
// 结果正好反过来：两件贵的凑一起往往超过 w，于是两件都得单独成组，
// 而两件便宜的凑一起白白浪费了一个名额。

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

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

    int cnt = 0;
    for (int i = 0; i < n; ) {
        if (i + 1 < n && a[i] + a[i + 1] <= w) { i += 2; }   // ← 相邻两个配
        else { i += 1; }
        cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

// P1094 的第二种贪心：★★★ 「每组尽量装满」（best-fit）—— 它**也是对的**
//
// ⚠⚠ 这份文件的注释被实测改写过一次，值得留个记录：
//   草稿里它是「错法三」，理由听起来很顺 —— best-fit（最佳适应）是**装箱问题**里的
//   经典近似启发式，而近似启发式当然不是最优解。
//   ⇒ **实测把这个说法打回来了。**
//   穷举 `n = 2..6`、`w = 4..14` 的**全部非降价格序列**（116 050 组）：**一个反例都没有**；
//   照题面随机、各种规模各种值域，也全是 0（页面第 ④ 步那几张表）。
//
// ★★★ 为什么它在这道题上是对的，而在装箱问题上不是 —— 差别就是题面那五个字：
//   **「每组最多两件」**。
//   一组只能放两件的时候，问题其实是「在一张阈值图上求最大匹配」，
//   而这种图上「最贵的配最便宜的」和「最贵的配最大能配的」**都能达到最大匹配**。
//   一旦允许每组三件，同一份 best-fit 当场就错（页面第 ⑤ 步实测：0 → 5 / 7 / 4）。
//
// ⇒ 所以这份文件真正的用处，是把「每组最多两件」这句约束**称出重量**：
//   它不是背景描述，是**命门** —— 有它，好几种贪心都对；没它，这题是 NP 难的装箱问题。
//
// 复杂度 O(n²)，比正解慢，只用来做对照。

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

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

    vector<char> used(n, 0);
    int cnt = 0;
    for (int i = n - 1; i >= 0; i--) {            // 从最贵的开始
        if (used[i]) continue;
        used[i] = 1;
        int best = -1;
        for (int j = 0; j < i; j++) {             // 找「加起来最接近 w」的搭档
            if (used[j]) continue;
            if (a[i] + a[j] > w) break;           // a 升序，再往后只会更大
            if (best < 0 || a[j] > a[best]) best = j;
        }
        if (best >= 0) used[best] = 1;
        cnt++;
    }
    cout << cnt << "\n";
    return 0;
}

// P1094 的度量程序 —— 这一页所有数字都出自这一份。
//
// `./p1094Count`      人看的版本
// `./p1094Count csv`  一行一项，给 scripts/check-viz.mjs 写断言用
//
// 五段：
//   ① ★ 双指针 ≡ 枚举所有分组方案（小数据，参照物完全离开贪心这条路）；
//   ② ★ 三个错法在**照题面随机**上各被抓多少；
//   ③ ★★★ best-fit 那个「看起来更聪明」的贪心的**最小反例**（穷举搜出来的）；
//   ④ ★★★ 它的抓获率由什么决定 —— 拧「P_i 的下限相对 w」这个旋钮；
//   ⑤ ★ 「循环写成 l < r」那个错法的触发条件：数一数「最后停在 l == r」的轮数，
//      看它是不是就等于被抓的轮数。

#include <bits/stdc++.h>
using namespace std;
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");
}

/** 正解：排序 + 对撞双指针。touch 记录「最后是不是停在 l == r」 */
static int solve(vector<int> a, int w, bool* touch = nullptr) {
    sort(a.begin(), a.end());
    int l = 0, r = (int)a.size() - 1, cnt = 0;
    if (touch) *touch = false;
    while (l <= r) {
        if (l == r && touch) *touch = true;
        if (a[l] + a[r] <= w) l++;
        r--;
        cnt++;
    }
    return cnt;
}
/** 错法一：l < r */
static int solveLt(vector<int> a, int w) {
    sort(a.begin(), a.end());
    int l = 0, r = (int)a.size() - 1, cnt = 0;
    while (l < r) { if (a[l] + a[r] <= w) l++; r--; cnt++; }
    return cnt;
}
/** 错法二：相邻两两配 */
static int solvePair(vector<int> a, int w) {
    sort(a.begin(), a.end());
    int n = a.size(), cnt = 0;
    for (int i = 0; i < n; ) { if (i + 1 < n && a[i] + a[i + 1] <= w) i += 2; else i += 1; cnt++; }
    return cnt;
}
/** 错法三：best-fit —— 每组尽量装满 */
static int solveFit(vector<int> a, int w) {
    sort(a.begin(), a.end());
    int n = a.size(), cnt = 0;
    vector<char> used(n, 0);
    for (int i = n - 1; i >= 0; i--) {
        if (used[i]) continue;
        used[i] = 1;
        int best = -1;
        for (int j = 0; j < i; j++) {
            if (used[j]) continue;
            if (a[i] + a[j] > w) break;
            if (best < 0 || a[j] > a[best]) best = j;
        }
        if (best >= 0) used[best] = 1;
        cnt++;
    }
    return cnt;
}
/** 参照物：枚举所有分组方案 */
static int gN, gW, gBest;
static vector<int> gA;
static vector<char> gUsed;
static void dfs(int done, int groups) {
    if (groups >= gBest) return;
    if (done == gN) { gBest = min(gBest, groups); return; }
    int i = 0;
    while (i < gN && gUsed[i]) i++;
    gUsed[i] = 1;
    dfs(done + 1, groups + 1);
    for (int j = i + 1; j < gN; j++) {
        if (gUsed[j] || gA[i] + gA[j] > gW) continue;
        gUsed[j] = 1;
        dfs(done + 2, groups + 1);
        gUsed[j] = 0;
    }
    gUsed[i] = 0;
}
static int brute(const vector<int>& a, int w) {
    gA = a; gN = a.size(); gW = w;
    gUsed.assign(gN, 0);
    gBest = gN + 1;
    dfs(0, 0);
    return gBest;
}

/** 照题面造一组：w ∈ [wLo, wHi]，P_i ∈ [pLo, w] */
static vector<int> gen(mt19937& rng, int n, int w, int pLo) {
    vector<int> a(n);
    for (int i = 0; i < n; i++) a[i] = pLo + (int)(rng() % (unsigned)(w - pLo + 1));
    return a;
}

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

    /* ① 双指针 ≡ 枚举所有分组方案 */
    {
        mt19937 rng(20260829u);
        int groups = 0, bad = 0;
        for (int rep = 0; rep < 400; rep++, groups++) {
            int w = 80 + (int)(rng() % 121);
            int n = (int)(rng() % 10) + 1;
            vector<int> a = gen(rng, n, w, 5);
            if (solve(a, w) != brute(a, w)) bad++;
        }
        if (!CSV) printf("① 双指针 vs 枚举所有分组方案：%d 组（n ≤ 10，值域照题面），不一致 %d 组\n", groups, bad);
        row("ref", {groups, bad});
    }

    /* ② 三个错法在照题面随机上的抓获率 */
    {
        mt19937 rng(555u);
        int lt = 0, pr = 0, ft = 0, touched = 0, ltTouch = 0;
        for (int r = 0; r < 300; r++) {
            int w = 80 + (int)(rng() % 121);
            int n = (int)(rng() % 10) + 1;
            vector<int> a = gen(rng, n, w, 5);
            bool touch; int ok = solve(a, w, &touch);
            if (touch) touched++;
            bool caught = solveLt(a, w) != ok;
            if (caught) { lt++; if (touch) ltTouch++; }
            if (solvePair(a, w) != ok) pr++;
            if (solveFit(a, w) != ok) ft++;
        }
        if (!CSV) printf("② 照题面随机 300 轮（n ≤ 10）：l<r 错 %d 次、相邻配对错 %d 次、best-fit 错 %d 次\n"
                         "   （「最后停在 l == r」的有 %d 轮，其中 l<r 被抓 %d 轮）\n",
                         lt, pr, ft, touched, ltTouch);
        row("catch", {lt, pr, ft, touched, ltTouch});
    }

    /* ③ ★★★ 找 best-fit 的反例 —— 结果是**找不到**，所以先证明这个搜索是活的 */
    {
        // 穷举 n = 2..6、w = 4..14 的**全部非降价格序列**，看有没有哪一组让某个写法错
        auto search = [&](int kind, int& fn, int& fw, vector<int>& fa) {
            fn = -1; fw = -1; fa.clear();
            for (int n = 2; n <= 6 && fn < 0; n++)
                for (int w = 4; w <= 14 && fn < 0; w++) {
                    vector<int> a(n, 1);
                    function<void(int, int)> rec = [&](int idx, int lo) {
                        if (fn >= 0) return;
                        if (idx == n) {
                            int got = kind == 0 ? solveFit(a, w) : solvePair(a, w);
                            if (got != brute(a, w)) { fn = n; fw = w; fa = a; }
                            return;
                        }
                        for (int v = lo; v <= w && fn < 0; v++) { a[idx] = v; rec(idx + 1, v); }
                    };
                    rec(0, 1);
                }
        };
        // 顺带数一数这个穷举一共看了多少组
        ll seqs = 0;
        for (int n = 2; n <= 6; n++)
            for (int w = 4; w <= 14; w++) {
                // 非降序列个数 = C(w + n - 1, n)
                long double c = 1;
                for (int i = 1; i <= n; i++) c = c * (w + n - i) / i;
                seqs += (ll)(c + 0.5L);
            }

        int fn, fw; vector<int> fa;
        search(0, fn, fw, fa);
        int fitFound = fn;
        int pn, pw; vector<int> pa;
        search(1, pn, pw, pa);

        if (!CSV) {
            printf("③ 穷举 n = 2..6、w = 4..14 的全部非降价格序列（共 %lld 组）：\n", seqs);
            printf("   · best-fit（每组尽量装满）：**一个反例都没有**（%s）\n",
                   fitFound < 0 ? "找不到" : "居然找到了");
            printf("   ⚠ 自检（证明这个搜索是活的）：同一个搜索对「相邻两两配」立刻找到反例 —— "
                   "n = %d，w = %d，价格 =", pn, pw);
            for (int x : pa) printf(" %d", x);
            printf("（它 %d 组，最优 %d 组）\n", solvePair(pa, pw), brute(pa, pw));
        }
        vector<ll> out = {seqs, fitFound < 0 ? 0 : 1, pn, pw};
        for (int x : pa) out.push_back(x);
        out.push_back(solvePair(pa, pw));
        out.push_back(brute(pa, pw));
        row("search", out);
    }

    /* ④ ★★★ 「每组最多两件」是命门：把它放宽到三件，同一个 best-fit 当场就错 */
    {
        // 最优解（每组最多 K 件）：枚举所有分组方案
        function<int(const vector<int>&, int, int)> bestK =
            [&](const vector<int>& a, int w, int K) {
                int n = a.size(), best = n + 1;
                vector<char> used(n, 0);
                function<void(int, int)> rec = [&](int done, int groups) {
                    if (groups >= best) return;
                    if (done == n) { best = min(best, groups); return; }
                    int i = 0;
                    while (i < n && used[i]) i++;
                    // 这一组以 i 打头，再从 i 之后挑最多 K-1 个，总和 ≤ w
                    vector<int> cand;
                    for (int j = i + 1; j < n; j++) if (!used[j]) cand.push_back(j);
                    int m = cand.size();
                    used[i] = 1;
                    for (int mask = 0; mask < (1 << m); mask++) {
                        if (__builtin_popcount(mask) > K - 1) continue;
                        int sum = a[i], k = 0;
                        for (int t = 0; t < m; t++) if (mask >> t & 1) { sum += a[cand[t]]; k++; }
                        if (sum > w) continue;
                        for (int t = 0; t < m; t++) if (mask >> t & 1) used[cand[t]] = 1;
                        rec(done + 1 + k, groups + 1);
                        for (int t = 0; t < m; t++) if (mask >> t & 1) used[cand[t]] = 0;
                    }
                    used[i] = 0;
                };
                rec(0, 0);
                return best;
            };
        // best-fit 的「每组最多 K 件」版本：从最贵的开始，反复塞进当前能塞的最大的一件
        auto fitK = [&](vector<int> a, int w, int K) {
            sort(a.begin(), a.end());
            int n = a.size(), cnt = 0;
            vector<char> used(n, 0);
            for (int i = n - 1; i >= 0; i--) {
                if (used[i]) continue;
                used[i] = 1;
                int sum = a[i];
                for (int k = 1; k < K; k++) {
                    int best = -1;
                    for (int j = 0; j < n; j++) {
                        if (used[j]) continue;
                        if (sum + a[j] > w) break;
                        if (best < 0 || a[j] > a[best]) best = j;
                    }
                    if (best < 0) break;
                    used[best] = 1;
                    sum += a[best];
                }
                cnt++;
            }
            return cnt;
        };

        const int WS[] = {8, 12, 20};
        vector<ll> out;
        int rounds = 300;
        for (int w : WS) {
            mt19937 rng(w * 2654435761u + 30u);
            int bad2 = 0, bad3 = 0;
            for (int r = 0; r < rounds; r++) {
                int n = 6 + (int)(rng() % 3);              // 6 ~ 8 件
                vector<int> a(n);
                for (int i = 0; i < n; i++) a[i] = 1 + (int)(rng() % (unsigned)w);
                if (fitK(a, w, 2) != bestK(a, w, 2)) bad2++;
                if (fitK(a, w, 3) != bestK(a, w, 3)) bad3++;
            }
            out.push_back(bad2); out.push_back(bad3);
            if (!CSV) printf("④ 同一份 best-fit（w = %2d，n = 6..8，%d 组）："
                             "每组最多 2 件时错 %d 次，放宽到最多 3 件时错 %d 次\n",
                             w, rounds, bad2, bad3);
        }
        row("capK", out);
    }

    /* ⑤ best-fit 在各档规模 / 值域上都没错（说明不是「没搜到」） */
    {
        const int NS[] = {4, 10, 30, 100};
        vector<ll> out;
        for (int n : NS) {
            mt19937 rng(n * 40503u + 9u);
            int bad = 0;
            for (int r = 0; r < 300; r++) {
                vector<int> a = gen(rng, n, 100, 5);
                if (solveFit(a, 100) != solve(a, 100)) bad++;
            }
            out.push_back(bad);
            if (!CSV) printf("⑤ w = 100，P_i ∈ [5, 100]，n = %3d：best-fit 和正解不同 %d / 300\n", n, bad);
        }
        row("fitN", out);
    }
    return 0;
}

// P1094 对拍生成器：`./p1094Gen <seed> [n 上限] [w 下限] [w 上限]`
//   默认 `n ≤ 10`、`w ∈ [80, 200]`、`P_i ∈ [5, w]` —— ★ 值域完全照题面。
//
// ⚠ 默认的 `n` 只到 10，因为参照物是**枚举所有分组方案**的暴力（跑不动大的）。
//   ★ 而这一页的重点恰好不在 n 上：三个错法里最难抓的那个（best-fit）
//     的抓获率主要由 **P_i 相对 w 的分布**决定 —— 页面第 ④ 步拧的是那个旋钮。

#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]) : 10;
    int wLo = argc > 3 ? atoi(argv[3]) : 80;
    int wHi = argc > 4 ? atoi(argv[4]) : 200;
    nHi = max(1, min(30000, nHi));
    wLo = max(2, min(200, wLo));
    wHi = max(wLo, min(200, wHi));

    mt19937 rng(seed * 2654435761u + 5u);
    int w = wLo + (int)(rng() % (unsigned)(wHi - wLo + 1));
    int n = (int)(rng() % (unsigned)nHi) + 1;
    printf("%d\n%d\n", w, n);
    for (int i = 0; i < n; i++)
        printf("%d\n", 5 + (int)(rng() % (unsigned)(w - 5 + 1)));   // 题面：5 ≤ P_i ≤ w
    return 0;
}