贪心的正确性：交换论证 + 用对拍打假错误贪心

// 找零钱 —— 贪心：从大到小，能拿就拿
//
// 题意：有 m 种面额的硬币（每种无限多，且一定包含面额 1），要凑出金额 x。
//       最少要几枚硬币？
//
// 这是全世界最容易骗到人的贪心，因为**在人民币的面额下它是对的**：
// 1 2 5 10 20 50 100，随便凑一个数，从大到小拿一定最省。
// 于是几乎所有人都会默认「找零钱当然贪心」。
//
// 但这个结论**属于那套面额，不属于这个算法**。换一套面额它立刻就错：
//     面额 {1, 3, 4}，要凑 6：
//       贪心 → 4 + 1 + 1 = 3 枚
//       最优 → 3 + 3     = 2 枚
// 就这么一个小到可以口算的例子，贪心就输了。
//
// 输入：第一行 m x，第二行 m 个面额
// 输出：贪心用的硬币数
//
// 用它和 coinDp.cpp 对拍，用 coinGen.cpp 造面额 —— 你会发现随机造一套面额，
// 它错的概率高得吓人。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    long long x;
    if (!(cin >> m >> x)) return 0;
    vector<long long> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];

    sort(c.begin(), c.end(), greater<long long>());   // 从大到小

    long long cnt = 0, left = x;
    for (int i = 0; i < m; i++) {
        cnt += left / c[i];        // 这种面额能拿几枚就拿几枚
        left %= c[i];
    }

    // 面额里有 1，所以一定凑得出来
    cout << cnt << "\n";
    return 0;
}

// 找零钱 —— 标准答案：DP（完全背包的最简形态）
//
// 为什么标准答案要用 DP 写，而不是「换一种贪心」：
// 对拍的两份程序**思路必须不同**。同一个想法写两遍，只能验出打字错误，验不出想法错误。
// 而这一章要抓的恰恰是想法错误。
//
// 状态：dp[i] = 凑出金额 i 最少要几枚硬币
// 转移：dp[i] = min(dp[i - c] + 1)，c 取遍所有面额
// 边界：dp[0] = 0（凑 0 块钱要 0 枚）
//
// 它为什么一定对：它**枚举了最后一枚硬币是哪种面额**，四种可能一种都没漏。
// 贪心则是「直接断定最后一枚（其实是第一枚）应该拿最大的」—— 断定得对不对，要证明。
// 这就是 DP 和贪心的全部区别：**DP 全试，贪心直接选。**
//
// 复杂度 O(xm)。x 到 10⁶ 都不成问题，比贪心慢，但慢得起。
// （这个 DP 就是第 24 章的完全背包，到那一章你会回来看这段代码。）
//
// 输入输出格式和 coinGreedy.cpp 完全一样。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    long long x;
    if (!(cin >> m >> x)) return 0;
    vector<long long> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];

    const long long INF = LLONG_MAX / 4;
    vector<long long> dp(x + 1, INF);
    dp[0] = 0;

    for (long long i = 1; i <= x; i++)
        for (int j = 0; j < m; j++)
            if (c[j] <= i && dp[i - c[j]] + 1 < dp[i])
                dp[i] = dp[i - c[j]] + 1;

    cout << (dp[x] >= INF ? -1 : dp[x]) << "\n";   // 面额里有 1 的话不会出现 -1
    return 0;
}

// 找零钱 —— 贪心：从大到小，能拿就拿
//
// 题意：有 m 种面额的硬币（每种无限多，且一定包含面额 1），要凑出金额 x。
//       最少要几枚硬币？
//
// 这是全世界最容易骗到人的贪心，因为**在人民币的面额下它是对的**：
// 1 2 5 10 20 50 100，随便凑一个数，从大到小拿一定最省。
// 于是几乎所有人都会默认「找零钱当然贪心」。
//
// 但这个结论**属于那套面额，不属于这个算法**。换一套面额它立刻就错：
//     面额 {1, 3, 4}，要凑 6：
//       贪心 → 4 + 1 + 1 = 3 枚
//       最优 → 3 + 3     = 2 枚
// 就这么一个小到可以口算的例子，贪心就输了。
//
// 输入：第一行 m x，第二行 m 个面额
// 输出：贪心用的硬币数
//
// 用它和 coinDp.cpp 对拍，用 coinGen.cpp 造面额 —— 你会发现随机造一套面额，
// 它错的概率高得吓人。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    long long x;
    if (!(cin >> m >> x)) return 0;
    vector<long long> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];

    sort(c.begin(), c.end(), greater<long long>());   // 从大到小

    long long cnt = 0, left = x;
    for (int i = 0; i < m; i++) {
        cnt += left / c[i];        // 这种面额能拿几枚就拿几枚
        left %= c[i];
    }

    // 面额里有 1，所以一定凑得出来
    cout << cnt << "\n";
    return 0;
}

// 找零钱 —— 给一套面额，把「最小的反例」找出来
//
// 为什么要有这份代码：
// 对拍能告诉你「你的贪心错了」，但它给你的那组数据往往又大又乱。
// 这份代码换个问法：**给定面额，最小的反例是多少？** 答案通常小得让人难堪 ——
// {1,3,4} 的最小反例是 6，{1,5,8} 的最小反例是 10。全都是能口算的数。
//
// ★ 顺带回答一个这一章绕不开的问题：**对拍没找到反例，能说明贪心是对的吗？**
// 一般情况下：**不能**。对拍只能证伪，不能证明（这一点正文里反复强调）。
//
// 但找零钱这道题有个漂亮的例外 —— Kozen–Zaks 定理（1994）：
//     如果一套面额 1 = c₁ < c₂ < … < cₘ 存在反例，
//     那么**最小的那个反例一定小于「最大的两个面额之和」cₘ₋₁ + cₘ**。
// 也就是说，只要在这个范围内扫一遍没找到反例，就可以断言这套面额永远安全 ——
// **有限的检查，换来了对无限多个 x 的保证。** 这才叫证明。
//
// 这份代码会把定理也一起验给你看：先在上界内找最小反例，
// 然后**故意再往外多扫 500**，确认上界外不会冒出「更早没发现」的意外。
//
// 输入：第一行 m，第二行 m 个面额（要包含 1）
// 输出：最小反例（如果有）、方案、以及定理的验证

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

static long long greedyCount(const vector<long long>& c, long long x, vector<long long>* plan) {
    long long cnt = 0, left = x;
    for (int i = (int)c.size() - 1; i >= 0; i--) {        // c 是升序，从大到小拿
        long long k = left / c[i];
        cnt += k;
        left %= c[i];
        if (plan) for (long long t = 0; t < k; t++) plan->push_back(c[i]);
    }
    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int m;
    if (!(cin >> m)) return 0;
    vector<long long> c(m);
    for (int i = 0; i < m; i++) cin >> c[i];
    sort(c.begin(), c.end());
    c.erase(unique(c.begin(), c.end()), c.end());
    m = (int)c.size();

    if (c[0] != 1) { cout << "面额里没有 1，可能有些金额根本凑不出来，先加上 1 再来。\n"; return 0; }

    long long bound = (m >= 2) ? c[m - 2] + c[m - 1] : c[m - 1] + 1;   // Kozen–Zaks 上界
    long long scan = bound + 500;                                       // 故意多扫一截

    // DP 求最少枚数，顺便记下「最后一枚拿的是哪种面额」，好把方案还原出来
    vector<long long> dp(scan + 1, LLONG_MAX / 4), from(scan + 1, -1);
    dp[0] = 0;
    for (long long i = 1; i <= scan; i++)
        for (int j = 0; j < m; j++)
            if (c[j] <= i && dp[i - c[j]] + 1 < dp[i]) { dp[i] = dp[i - c[j]] + 1; from[i] = c[j]; }

    cout << "面额：";
    for (int i = 0; i < m; i++) cout << c[i] << " \n"[i == m - 1];

    long long first = -1, firstOutside = -1;
    for (long long x = 1; x <= scan; x++) {
        if (greedyCount(c, x, nullptr) > dp[x]) {
            if (first < 0) first = x;
            if (x >= bound && firstOutside < 0) firstOutside = x;
        }
    }

    if (first < 0) {
        cout << "扫到 " << scan << " 都没有反例 —— 这套面额下贪心永远是对的。\n";
        cout << "而且根据 Kozen–Zaks 定理，只要扫到 " << bound
             << "（最大的两个面额之和）没出事就够了，后面那 500 个是白扫的。\n";
        return 0;
    }

    vector<long long> gp, bp;
    greedyCount(c, first, &gp);
    for (long long v = first; v > 0; v -= from[v]) bp.push_back(from[v]);

    auto show = [](const vector<long long>& p) {
        string s;
        for (size_t i = 0; i < p.size(); i++) { if (i) s += " + "; s += to_string(p[i]); }
        return s;
    };

    cout << "最小反例：x = " << first << "\n";
    cout << "  贪心 " << gp.size() << " 枚：" << show(gp) << "\n";
    cout << "  最优 " << bp.size() << " 枚：" << show(bp) << "\n";
    cout << "Kozen–Zaks 上界 = 最大两个面额之和 = " << bound
         << "，定理说最小反例必定小于它：" << first << " < " << bound
         << (first < bound ? "  ✓ 成立" : "  ✗ 居然不成立？") << "\n";
    cout << "又往外多扫了 500，"
         << (firstOutside < 0 ? "上界之外没有出现任何新反例。\n"
                              : "上界之外也有反例，但那不重要 —— 定理保证的是「最小的那个」在上界内。\n");
    return 0;
}

// 01 背包 —— 按性价比贪心（**这是错的**，这一章就是要打假它）
//
// 「先拿性价比最高的」听起来天经地义：每一公斤都要花得最值。
// 而且它在**部分背包**（物品可以切开卖，见 fracKnap.cpp）里是**完全正确**的，
// 有严格的交换论证。很多人就是这么被带进沟里的。
//
// 但 01 背包不能切。于是会发生这种事：
//
//     W = 50，三件物品
//       A: 价值 60，重 10 → 性价比 6.0
//       B: 价值 100，重 20 → 性价比 5.0
//       C: 价值 120，重 30 → 性价比 4.0
//
//     贪心：拿 A(10)、拿 B(20)，剩 20 的空间装不下 C → 160
//     最优：B + C = 220
//
// 差了 60。而且注意：**贪心一步都没走错**，每一步都拿了当时性价比最高的、装得下的。
// 错的是「每一步局部最优 ⇒ 整体最优」这个假设本身。
//
// ★ 交换论证为什么在这里失效：
//   部分背包里，把一件低性价比的货换成高性价比的，「同样的重量换来更多价值」，一定不亏。
//   01 背包里你**换不了那个重量** —— 高性价比那件只有一件，且重量固定，
//   换进来会留下一个填不满的空隙，而空隙是白白浪费的。
//   **论证卡在哪里，反例就在哪里。**
//
// 输入输出格式和 knapBrute.cpp 一样。
// 拿它和 knapBrute.cpp 对拍，通常两三轮之内就会被抓。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    vector<int> id(n);
    for (int i = 0; i < n; i++) id[i] = i;

    // 按 v/w 从大到小。用交叉相乘比较，别用浮点除法 —— 浮点比较是另一个坑，
    // v1/w1 > v2/w2 等价于 v1*w2 > v2*w1（w 都是正数）。
    sort(id.begin(), id.end(), [&](int a, int b) {
        long long lhs = v[a] * w[b], rhs = v[b] * w[a];
        return lhs != rhs ? lhs > rhs : w[a] < w[b];
    });

    long long left = W, got = 0;
    for (int i : id)
        if (w[i] <= left) { left -= w[i]; got += v[i]; }

    cout << got << "\n";
    return 0;
}

// 01 背包 —— 三种贪心 + 最优解 + 部分背包，五行并排
//
// 为什么要有这份代码：
// 「按性价比排」错了之后，很多人的第一反应是「那我换个排法」——
// 换成按价值大的先拿？换成按重量小的先拿？这份代码一次性回答：**三种全错。**
//
// 而第五行是这一章的题眼：**同一份数据、同一个「按性价比」的贪心，
// 只要允许把物品切开，它立刻变成最优的。**
//
// 也就是说：
//     贪心的正确性不是算法的属性，是**问题的属性**。
//     「这个贪心对不对」这句话本身就问错了 —— 得问「这个贪心在这个问题上对不对」。
//
// 输入输出格式和 knapBrute.cpp 一样，输出是一张五行的表。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    vector<int> id(n);
    for (int i = 0; i < n; i++) id[i] = i;

    // 三种排法，装法完全一样：顺着看，装得下就装。差别百分之百来自排序。
    auto pack = [&](vector<int> order) {
        long long left = W, got = 0;
        for (int i : order) if (w[i] <= left) { left -= w[i]; got += v[i]; }
        return got;
    };

    vector<int> byV = id, byW = id, byR = id;
    sort(byV.begin(), byV.end(), [&](int a, int b) { return v[a] != v[b] ? v[a] > v[b] : w[a] < w[b]; });
    sort(byW.begin(), byW.end(), [&](int a, int b) { return w[a] != w[b] ? w[a] < w[b] : v[a] > v[b]; });
    sort(byR.begin(), byR.end(), [&](int a, int b) {
        long long lhs = v[a] * w[b], rhs = v[b] * w[a];
        return lhs != rhs ? lhs > rhs : w[a] < w[b];
    });

    long long best = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
        long long sw = 0, sv = 0;
        for (int i = 0; i < n; i++) if (mask >> i & 1) { sw += w[i]; sv += v[i]; }
        if (sw <= W) best = max(best, sv);
    }

    // 第五行：同一个「按性价比」的贪心，但允许切开
    long long left = W, whole = 0;
    double extra = 0;
    for (int i : byR) {
        if (left <= 0) break;
        if (w[i] <= left) { left -= w[i]; whole += v[i]; }
        else { extra = (double)v[i] * (double)left / (double)w[i]; left = 0; }
    }

    long long r1 = pack(byV), r2 = pack(byW), r3 = pack(byR);
    auto tag = [&](long long r) { return r == best ? "" : "   ← 比最优少"; };

    cout << "策略                          总价值\n";
    cout << "① 先拿价值最大的                " << r1 << tag(r1) << "\n";
    cout << "② 先拿重量最小的                " << r2 << tag(r2) << "\n";
    cout << "③ 先拿性价比最高的              " << r3 << tag(r3) << "\n";
    cout << "④ 枚举全部子集（一定最优）      " << best << "\n";
    cout << "⑤ 同一个③，但允许切开（部分背包）  " << fixed << setprecision(2)
         << (double)whole + extra << "\n";

    if (r1 == best && r2 == best && r3 == best)
        cout << "\n这组数据太温柔了，三种贪心都蒙对了 —— 换一组再试。\n";
    return 0;
}

// 部分背包 —— 同一个贪心，在这里是**对的**
//
// 和 knapGreedy.cpp 唯一的区别：物品可以**切开**（金粉、大米这类），
// 拿走一半的重量就得到一半的价值。
//
// 于是那个「先拿性价比最高的」贪心立刻变成正确的，而且能证明：
//
// ★ 交换论证：设最优解里装了一部分低性价比的货 y，同时还有高性价比的货 x 没装满。
//   把 y 拿出来一点点（重量 δ），换成同样重量的 x。
//   总重量没变，而价值变化 = δ·(x的性价比 − y的性价比) > 0 —— 严格变好。
//   所以最优解里不可能出现「x 没装满却装了 y」，
//   也就是说最优解一定是「性价比从高到低，能装多少装多少，最后一件切开」。∎
//
//   ⚠ 这段论证里**唯一**用到「可以切开」的地方，就是「拿出来一点点、换进去一点点」。
//   01 背包不能切，这一步立刻做不下去 —— 论证在哪里断掉，反例就在哪里。
//   **这就是这一章最想让你记住的读法：不要背结论，要盯着论证在哪一步用到了题目的条件。**
//
// 输入输出格式和 knapBrute.cpp 一样，只是答案可能不是整数，保留两位小数。
//
// ⚠ 顺带一个坑：答案是浮点数，对拍时**不能用 == 比较**（见正文）。
//   这份代码里凡是能用整数的地方都用整数，只在最后切开那一件时才动浮点。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    vector<int> id(n);
    for (int i = 0; i < n; i++) id[i] = i;
    sort(id.begin(), id.end(), [&](int a, int b) {
        long long lhs = v[a] * w[b], rhs = v[b] * w[a];
        return lhs != rhs ? lhs > rhs : w[a] < w[b];
    });

    long long left = W, whole = 0;      // 整件装进去的部分，全程整数
    double extra = 0;                   // 最后切开的那一件，只有这里是浮点
    for (int i : id) {
        if (left <= 0) break;
        if (w[i] <= left) { left -= w[i]; whole += v[i]; }
        else { extra = (double)v[i] * (double)left / (double)w[i]; left = 0; }
    }

    cout << fixed << setprecision(2) << (double)whole + extra << "\n";
    return 0;
}

// 01 背包 —— 按性价比贪心（**这是错的**，这一章就是要打假它）
//
// 「先拿性价比最高的」听起来天经地义：每一公斤都要花得最值。
// 而且它在**部分背包**（物品可以切开卖，见 fracKnap.cpp）里是**完全正确**的，
// 有严格的交换论证。很多人就是这么被带进沟里的。
//
// 但 01 背包不能切。于是会发生这种事：
//
//     W = 50，三件物品
//       A: 价值 60，重 10 → 性价比 6.0
//       B: 价值 100，重 20 → 性价比 5.0
//       C: 价值 120，重 30 → 性价比 4.0
//
//     贪心：拿 A(10)、拿 B(20)，剩 20 的空间装不下 C → 160
//     最优：B + C = 220
//
// 差了 60。而且注意：**贪心一步都没走错**，每一步都拿了当时性价比最高的、装得下的。
// 错的是「每一步局部最优 ⇒ 整体最优」这个假设本身。
//
// ★ 交换论证为什么在这里失效：
//   部分背包里，把一件低性价比的货换成高性价比的，「同样的重量换来更多价值」，一定不亏。
//   01 背包里你**换不了那个重量** —— 高性价比那件只有一件，且重量固定，
//   换进来会留下一个填不满的空隙，而空隙是白白浪费的。
//   **论证卡在哪里，反例就在哪里。**
//
// 输入输出格式和 knapBrute.cpp 一样。
// 拿它和 knapBrute.cpp 对拍，通常两三轮之内就会被抓。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    long long W;
    if (!(cin >> n >> W)) return 0;
    vector<long long> v(n), w(n);
    for (int i = 0; i < n; i++) cin >> v[i] >> w[i];

    vector<int> id(n);
    for (int i = 0; i < n; i++) id[i] = i;

    // 按 v/w 从大到小。用交叉相乘比较，别用浮点除法 —— 浮点比较是另一个坑，
    // v1/w1 > v2/w2 等价于 v1*w2 > v2*w1（w 都是正数）。
    sort(id.begin(), id.end(), [&](int a, int b) {
        long long lhs = v[a] * w[b], rhs = v[b] * w[a];
        return lhs != rhs ? lhs > rhs : w[a] < w[b];
    });

    long long left = W, got = 0;
    for (int i : id)
        if (w[i] <= left) { left -= w[i]; got += v[i]; }

    cout << got << "\n";
    return 0;
}

// 区间调度 —— 按左端点从早到晚（**这是错的**）
//
// 这份代码是第 19 章那道题的「错误版」，放在这一章是为了让你亲手对拍它。
// 除了排序的那一行，它和 code/19-greedy-sorting/itvFast.cpp **一模一样**。
//
// 「早点开始，就能多参加几场」—— 听起来毫无破绽，但它把「开始得早」
// 和「结束得早」这两件事混为一谈了。一场从早开到晚的比赛开始得最早，
// 却把整天都占掉了。
//
// 最小的反例只有三场比赛：
//     [1,10]、[2,3]、[4,5]  →  它选 1 场，最优 2 场。
//
// 用它和第 19 章的 itvBrute.cpp 对拍（生成器也用那一章的 itvGen.cpp），
// 通常两三轮之内就会被打假。
//
// 冲突的约定和第 19 章一致：**端点重合不算冲突**（[1,3] 和 [3,5] 可以都参加）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> a(n);       // (l, r)
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

    sort(a.begin(), a.end());                      // ← 错就错在这一行：按左端点排

    int cnt = 0;
    long long lastEnd = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        if (a[i].first >= lastEnd) { cnt++; lastEnd = a[i].second; }
    }

    cout << cnt << "\n";
    return 0;
}

// 区间调度 —— 按左端点从早到晚（**这是错的**）
//
// 这份代码是第 19 章那道题的「错误版」，放在这一章是为了让你亲手对拍它。
// 除了排序的那一行，它和 code/19-greedy-sorting/itvFast.cpp **一模一样**。
//
// 「早点开始，就能多参加几场」—— 听起来毫无破绽，但它把「开始得早」
// 和「结束得早」这两件事混为一谈了。一场从早开到晚的比赛开始得最早，
// 却把整天都占掉了。
//
// 最小的反例只有三场比赛：
//     [1,10]、[2,3]、[4,5]  →  它选 1 场，最优 2 场。
//
// 用它和第 19 章的 itvBrute.cpp 对拍（生成器也用那一章的 itvGen.cpp），
// 通常两三轮之内就会被打假。
//
// 冲突的约定和第 19 章一致：**端点重合不算冲突**（[1,3] 和 [3,5] 可以都参加）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;
    vector<pair<long long, long long>> a(n);       // (l, r)
    for (int i = 0; i < n; i++) cin >> a[i].first >> a[i].second;

    sort(a.begin(), a.end());                      // ← 错就错在这一行：按左端点排

    int cnt = 0;
    long long lastEnd = LLONG_MIN;
    for (int i = 0; i < n; i++) {
        if (a[i].first >= lastEnd) { cnt++; lastEnd = a[i].second; }
    }

    cout << cnt << "\n";
    return 0;
}