P4809 蛋糕装盒（基础）

解题思路

1. 读懂题目：有 x 个蛋糕和 y 个盒子，一个盒子只能装一个蛋糕，盒子的容积必须 ≥ 蛋糕的体积。盒子价格等于它的容积。问花最少的钱能不能把蛋糕全部装完，能的话输出最少钱数，不能就输出 -1。

2. 打个比方：就像给大小不同的球找盒子，大球应该用"刚好能装下它"的最小的盒子，把更大的盒子留给更大的球，这样才不会浪费。

3. 第一步：把蛋糕体积从大到小排序，盒子容积从小到大排序。

4. 第二步：从最大的蛋糕开始处理。为它找一个"容积 ≥ 它的体积、并且还没被用掉"的最小的盒子，花的钱就是这个盒子的容积，累加到答案里。

5. 第三步：怎么快速找到这个盒子？用树状数组（Binary Indexed Tree）维护每个盒子是不是还能用：先用二分找出第一个容积 ≥ 蛋糕体积的盒子位置，再通过树状数组找到这个位置之后的第一个可用盒子。

6. 第四步：如果某个蛋糕连最大的盒子都装不下（二分找到的位置到了数组末尾），或者能装下它的盒子都已经用完了，就说明装不下，输出 -1。

7. 为什么贪心正确：最大的蛋糕必须用能装下它的盒子，给它用"最小的合适盒子"，就能把更大的盒子留给后面更小的蛋糕，总钱数最少。

8. 边界情况：蛋糕和盒子的体积可能很大，总钱数要用 long long 存；盒子容积刚好等于蛋糕体积也能装。

参考代码

// P4809 蛋糕装盒：蛋糕从大到小装，每个蛋糕找能装下的最小盒子，用树状数组快速找可用盒子
#include <iostream>
#include <algorithm>
using namespace std;

long long cake[100005];  // 蛋糕体积
long long box[100005];   // 盒子容积，从小到大排序
int bit[100005];         // 树状数组，记录每个位置还有没有可用盒子
int n;                   // 盒子总个数

// 树状数组：把下标 idx（从 1 开始）加上 delta
void bitAdd(int idx, int delta) {
    for (; idx <= n; idx += idx & (-idx)) bit[idx] += delta;
}

// 树状数组：前 idx 个盒子里还有几个可用
int bitSum(int idx) {
    int res = 0;
    for (; idx > 0; idx -= idx & (-idx)) res += bit[idx];
    return res;
}

// 找到第 target 个可用盒子的位置（返回 1 开始的下标）
int kth(int target) {
    int idx = 0;
    int step = 1;
    while (step * 2 <= n) step *= 2;
    for (; step > 0; step >>= 1) {
        int next = idx + step;
        if (next <= n && bit[next] < target) {
            idx = next;
            target -= bit[next];
        }
    }
    return idx + 1;
}

int main() {
    int x, y;
    cin >> x >> y;
    for (int i = 0; i < x; i++) cin >> cake[i];
    for (int i = 0; i < y; i++) cin >> box[i];
    // 蛋糕从小到大、盒子从小到大排序，蛋糕从大的开始装
    sort(cake, cake + x);
    sort(box, box + y);
    n = y;
    for (int i = 1; i <= y; i++) bitAdd(i, 1);   // 一开始所有盒子都可用
    long long ans = 0;   // 用掉的盒子花的钱
    for (int i = x - 1; i >= 0; i--) {
        // 找到第一个容积 >= 这块蛋糕体积的盒子（下标 0 开始）
        int pos = lower_bound(box, box + y, cake[i]) - box;
        if (pos == y) {
            cout << -1 << endl;   // 连最大的盒子都装不下，无法全部装盒
            return 0;
        }
        // pos 之前可用的盒子数 + 1，就是能装下这块蛋糕的最小可用盒子
        int target = bitSum(pos) + 1;
        if (target > bitSum(y)) {
            cout << -1 << endl;   // 能装下的盒子都被用完了
            return 0;
        }
        int idx = kth(target) - 1;   // 转成 0 开始的下标
        ans += box[idx];
        bitAdd(idx + 1, -1);   // 这个盒子被用掉了
    }
    cout << ans << endl;
    return 0;
}

复杂度分析

排序需要 O(x log x + y log y)；每个蛋糕用树状数组找一个可用盒子需要 O(log y)，一共 x 个蛋糕。所以总时间复杂度是 O((x+y) log y)，完全够处理 10 万的数据。空间上需要两个数组存蛋糕和盒子，空间复杂度是 O(x + y)。