16 · 贪心入门：交换论证与排序贪心

贪心只有一句话：每一步都选当前看起来最好的，并且永不回头。难的不是“选最好的”，而是判断“这样选会不会毁掉全局”。本节把它变成一张 6 行的检查表，再用交换论证把“排序贪心”钉死——改一行 cmp 就换了一个算法，所以那一行必须有证明撑着。

先看判断清单。它不能保证贪心一定对，但能让你在 5 分钟内决定：继续想贪心，还是立刻换成 DP / 搜索。

上表里的两个反例值得记一辈子，因为它们把“贪心为什么会错”说透了。硬币：面值 1、3、4，凑 6。贪心先拿最大的 4，剩 2 只能 1 + 1，共 3 枚；最优是 3 + 3，两枚。0/1 背包：容量 20。A 件重 10 值 60（性价比 6），B 件重 20 值 100（性价比 5）。按性价比先拿 A，剩 10 装不下 B，得 60；最优是只拿 B，得 100。两者的共同结构：局部最优消耗了一份“未来资源”，而这份资源的价格没有被算进当前收益。

接水问题为什么没有这个毛病？每个人只占 1 个位置，位置总数固定为 n，谁占都不改变“后面还有几个人要等”。资源不被消耗，只是被排序，所以排序就能解决。这一条判据后面会反复出现：如果“选择”只是在重排一个定长的序列，贪心往往成立；如果“选择”会减少未来可用的资源，贪心往往不成立。

本节没有新库函数，但有一个必须吃透的东西：cmp。在排序贪心里，cmp 就是算法本身。

struct Node { int t, id; } a[1005];

bool cmp(const Node &x, const Node &y) {
    if (x.t != y.t) return x.t < y.t;   // 主键：接水时间短的优先
    return x.id < y.id;                 // 次键：时间相同按编号，输出稳定
}

sort(a + 1, a + n + 1, cmp);            // 排序只做一件事：把 cmp 认为"优先"的放前面

现在用一道最经典的题把上面的东西落地：排队接水。它的搜索空间大到不可能枚举，但它的结构简单到只需要一次排序。

sort(a + 1, a + n + 1, cmp);                              // 贪心的全部内容：按 T 升序
long long sum = 0;
for (int i = 1; i <= n; ++i) sum += 1LL * a[i].t * (n - i);   // 贡献法

下面是完整程序。n 只有 1000，但用 sort 已经是习惯：同样的写法换到 n = 10⁶ 也不用改。

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

const int N = 1005;
int n;
struct Node {
    int t;      // 接水用时
    int id;     // 原始编号：排序会打乱位置，编号必须跟着走
} a[N];

// 贪心策略：接水时间短的先上
bool cmp(const Node &x, const Node &y) {
    if (x.t != y.t) return x.t < y.t;   // 主键：时间升序
    return x.id < y.id;                 // 次键：时间相同，编号小的在前
}

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

    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i].t;
        a[i].id = i;                    // 记住它原本是第几个人
    }
    sort(a + 1, a + n + 1, cmp);        // O(n log n)，n = 1000 时约 1 万次比较

    long long sum = 0;                  // 总等待时间可达 5*10^11，int 装不下
    for (int i = 1; i <= n; ++i) {
        sum += 1LL * a[i].t * (n - i);  // 第 i 位的人被后面 n-i 人各等一次
        if (i > 1) cout << ' ';         // 分隔符：第一个数前面不打空格
        cout << a[i].id;
    }
    cout << '\n';
    cout << fixed << setprecision(2) << 1.0 * sum / n << '\n';
    return 0;
}

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

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

    string s;
    int k;
    cin >> s >> k;

    // 删 k 次，每次删掉"第一个比后一位大的数字"
    for (int step = 0; step < k; ++step) {
        int i = 0;
        // 找第一个下降点 s[i] > s[i+1]；找不到时 i 会停在最后一位
        while (i + 1 < (int)s.size() && s[i] <= s[i + 1]) ++i;
        s.erase(s.begin() + i);     // 删掉它（单调不降时删的就是末位）
    }

    // 去前导零，但至少留一位
    int p = 0;
    while (p + 1 < (int)s.size() && s[p] == '0') ++p;

    cout << s.substr(p) << '\n';
    return 0;
}