Day 14 · 贪心进阶：区间、背包、堆

题意：有 n 场比赛，每场知道开始时间和结束时间。参加一场就必须从头参加到尾， 而且不能同时参加两场。问最多能参加几场。

思路

贪心策略：按结束时间升序排序，然后从头到尾扫一遍，能接上就选。

第 1 节已经用交换论证证过：结束最早的那场，一定可以放进某个最优解里。 选完它之后，剩下的问题和原问题一样，所以可以一直贪下去。

实现起来非常简单：记一个 lastEnd（上一场选中的结束时间）， 遇到 s >= lastEnd 的比赛就选它，并更新 lastEnd。

3
0 2
2 4
1 3

2

按结束时间排序后是 [0,2]、[1,3]、[2,4]。
选 [0,2] → lastEnd = 2；
[1,3] 的 1 < 2，接不上，跳过；
[2,4] 的 2 ≥ 2，能接上，选它 → 共 2 场。
注意这里 [0,2] 和 [2,4] 端点相接是可以的，所以判断用的是 >=。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

struct Match {
    int s;   // 开始时间
    int e;   // 结束时间
};

Match a[1000005];           // ★ n 最大 10^6，数组要开够

// 按右端点（结束时间）从小到大排序
bool cmp(const Match &p, const Match &q){
    return p.e < q.e;       // ★ 是 e 不是 s ！按开始时间排就错了
}

int main(){
    ios::sync_with_stdio(false);   // ★ n 最大 10^6，关掉同步加速读入
    cin.tie(0);

    int n;
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> a[i].s >> a[i].e;
    }
    sort(a, a + n, cmp);

    int ans = 0;
    int lastEnd = -1;              // 上一场选中的比赛的结束时间
    for(int i = 0; i < n; i++){
        if(a[i].s >= lastEnd){     // ★ 是 >= ，端点相接算不冲突
            ans++;
            lastEnd = a[i].e;
        }
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 按开始时间排序：这是最经典的错误。第 1 节的反例 [0,100] [1,2] [3,4] 会算出 1，正确答案是 2。
• 判断写成 a[i].s > lastEnd：端点相接的比赛会被漏掉。本题样例就依赖 >=， 如果写成 >，样例输出会变成 1 而不是 2。
• lastEnd 初值写 0：本题 aᵢ ≥ 0，用 0 也能过；但如果题目允许开始时间是负数就会出错。 用 -1 更稳。
• 数组开太小：n 能到 10⁶，开 100000 是必挂的。
• 不关同步：10⁶ 行输入，用默认的 cin 可能超时。

题意：N 堆金币，第 i 堆总重 mᵢ、总价值 vᵢ。背包承重 T。金币可以随意分割， 切割后单位价值不变。问最多能拿走多少价值的金币，输出两位小数。

思路

第 2 节已经讲清楚了：按性价比（单位价值 v/m）从高到低排序，能全拿就全拿，装不下就切一部分。

实现上有两个小要点：

• 排序前要先把性价比算出来存进结构体，不然 cmp 里每次都得重算一遍除法（慢，而且容易写错）。
• 一旦遇到「装不下」的那一堆，切完就 break。 因为后面所有堆的性价比都更低，装它们还不如装当前这堆剩下的部分。

4 50
10 60
20 100
25 100
15 45

240.00

性价比：第 1 堆 60/10 = 6.0（最高）、第 2 堆 100/20 = 5.0、第 3 堆 100/25 = 4.0、第 4 堆 45/15 = 3.0。
按这个顺序拿：全拿第 1 堆（用掉 10，剩 40，价值 60）；
全拿第 2 堆（用掉 20，剩 20，价值 160）；
第 3 堆需要 25 但只剩 20 → 切 20/25 = 0.8 份，价值 100 × 0.8 = 80；
背包满了，结束。总价值 60 + 100 + 80 = 240.00。

完整代码

#include <iostream>
#include <algorithm>
#include <iomanip>
using namespace std;

struct Heap {
    double m;   // 总重量
    double v;   // 总价值
    double r;   // 单位价值（性价比）= v / m
};

Heap a[105];

// 按性价比从高到低排序
bool cmp(const Heap &p, const Heap &q){
    return p.r > q.r;        // ★ 降序！用 > 不是 <
}

int main(){
    int n;
    double T;                // 背包容量，会参与小数运算
    cin >> n >> T;
    for(int i = 0; i < n; i++){
        cin >> a[i].m >> a[i].v;
        a[i].r = a[i].v / a[i].m;    // 提前算好性价比存起来
    }
    sort(a, a + n, cmp);

    double ans = 0;
    for(int i = 0; i < n; i++){
        if(T >= a[i].m){
            // 背包还装得下整堆，全拿走
            ans += a[i].v;
            T -= a[i].m;
        } else {
            // 装不下了：把这堆切下来 T 重量，后面的一律不用看了
            ans += a[i].r * T;
            T = 0;
            break;
        }
    }
    cout << fixed << setprecision(2) << ans << "\n";
    return 0;
}

易错点

• 按总价值排序：应该按单位价值（性价比）。一堆又重又贵的金子，不一定比一堆轻便的更划算。
• 按重量排序：轻的不一定划算，同样错。
• cmp 写成升序 p.r < q.r：那会先拿性价比最低的，答案错得离谱。
• 用 int 存 m 和 v：v / m 会是整数除法，性价比全变成整数（比如 60/10 得 6，但 45/15 也会得 3， 而 100/25 得 4 —— 凑巧还行，但换成 7/2 就得 3 而不是 3.5，全错）。必须用 double。
• 最后切的时候写 ans += a[i].v：那是整堆的价值，应该按比例算 a[i].r * T。
• 忘了 fixed << setprecision(2)：输出会变成 240 而不是 240.00，格式错误。

题意：有 n 堆果子，每次可以把两堆合并成新的一堆，消耗的体力等于两堆重量之和。 合并 n−1 次之后就只剩一堆。问总共消耗的体力最小是多少。

思路

贪心策略：每次合并当前最小的两堆。

为什么？想成一棵树：把合并过程画出来，最后合成的那一大堆放最上面， 越早被合并的果子堆在树里位置越深。

直观的比方：搬东西的时候，重的东西少搬两趟、轻的东西多搬两趟，总力气最省。反过来就亏了。

实现：用小根堆。每次弹出最小的两个，相加累加到答案里，再把新堆塞回堆里。重复到只剩一堆。

3
1 2 9

15

先合并 1 和 2 → 得到 3，消耗 3；再合并 3 和 9 → 得到 12，消耗 12。总共 3 + 12 = 15。
如果先合并 2 和 9（消耗 11），再和 1 合并（消耗 12），总共 23，明显更差 —— 这就是「先拿小的」的价值。

完整代码

#include <iostream>
#include <queue>
#include <vector>
#include <functional>
using namespace std;

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

    int n;
    cin >> n;

    // ★ 小根堆：永远能从堆顶取到当前最小的那堆果子
    //   三个参数分别是：元素类型、底层容器、比较器
    priority_queue<int, vector<int>, greater<int> > pq;

    for(int i = 0; i < n; i++){
        int x;
        cin >> x;
        pq.push(x);              // 自己会排好，不用管
    }

    long long ans = 0;           // ★ 用 long long 保险
    while(pq.size() > 1){        // 合并到只剩一堆为止
        int x = pq.top(); pq.pop();   // 第一小
        int y = pq.top(); pq.pop();   // 第二小
        ans += x + y;                 // 合并的体力 = 两堆重量之和
        pq.push(x + y);               // ★ 合并成的新堆放回堆里，参与后面的合并
    }
    cout << ans << "\n";
    return 0;
}

易错点

• 小根堆的模板参数写错：要写 priority_queue<int, vector<int>, greater<int> >。 写成 priority_queue<int> 会变成大根堆（每次取最大的两堆），答案会大很多。
• 忘了把新堆塞回去：合并出来的新堆还要参与后面的合并，pq.push(x + y) 不能漏。
• pop() 之后还想用那个值：pop() 不返回值，必须先 top() 存下来再 pop()。
• 循环条件写成 while(!pq.empty())：只剩一堆时还会试图弹两个，程序直接崩。
• 用 int 存答案：极端数据下会超（我实测到 2672320000），用 long long 零成本保平安。
• 排序 + 双指针：这题不能排序后简单地从左往右配对 —— 因为合并出的新堆要重新参与比较， 位置会插到中间去。这正是必须用堆的原因。

题意：需要采购总量 n 的牛奶，有 m 个奶农，第 i 个奶农的单价是 pᵢ、每天最多能卖 aᵢ。 可以从某个奶农那里买不超过他产量的任意整数数量。问买够 n 最少花多少钱。

思路

和 P2240 是同一个套路，只是牛奶本身就是连续的（可以买任意整数升），所以更简单：

实现只要一个循环：

for 每个奶农（已按单价升序）:
    take = min(还需要的量, 这家产量)
    cost += take * 单价
    还需要的量 -= take

100 5
5 20
9 40
3 10
8 80
6 30

630

按单价排序：(3, 10)、(5, 20)、(6, 30)、(8, 80)、(9, 40)。
买 10 升 @3 = 30（还差 90）→ 买 20 升 @5 = 100（还差 70）→ 买 30 升 @6 = 180（还差 40）→ 买 40 升 @8 = 320（够了，停）。
总计 30 + 100 + 180 + 320 = 630。注意最后一个奶农（单价 9）一元都没买，因为前面就够了。

完整代码

#include <iostream>
#include <algorithm>
using namespace std;

struct Farmer {
    long long p;   // 单价
    long long a;   // 最多能卖的牛奶量
};

Farmer f[5005];

// 按单价从小到大排序
bool cmp(const Farmer &x, const Farmer &y){
    return x.p < y.p;      // ★ 升序：先买便宜的
}

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

    long long n;   // 需要的总奶量（最大 2×10^6）
    int m;         // 奶农个数（最大 5000）
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        cin >> f[i].p >> f[i].a;
    }
    sort(f, f + m, cmp);

    long long cost = 0;                // ★ 最贵能到 2×10^9，必须 long long
    for(int i = 0; i < m && n > 0; i++){  // ★ n > 0：买够了就提前退出
        long long take = min(n, f[i].a);   // 这家人最多能给这么多
        cost += take * f[i].p;
        n -= take;
    }
    cout << cost << "\n";
    return 0;
}

易错点

• 用 int 存总花费：能到 2×10⁹，紧贴 int 上限，非常危险。
• take 用 int：min(n, f[i].a) 如果 n 是 long long 而 f[i].a 是 int， 会有一个隐式转换；两边都声明成 long long 最省心。
• 排序按产量排：应该按单价排。产量大但很贵的奶农不值得先买。
• 忘了 n > 0 提前退出：虽然结果一样（min(0, a) = 0），但会白跑循环； 而且如果 n 变成负数，跑下去就可能算错。
• 以为 m ≥ 1：题面写的是 0 ≤ m，虽然实际数据里 m = 0 意味着 n 也只能是 0，但代码不该崩在这个上面。
• 读入顺序搞反：第一行是「需要量 n」在前、「奶农个数 m」在后； 每行是「单价 pᵢ」在前、「产量 aᵢ」在后。样例里第一行是 100 5，别读成 5 100。