PA 2019 Runda 4 Szprotki i szczupaki 题解

题目分析

这道题要求模拟鲨鱼吃小鱼的过程，支持动态添加和删除小鱼，并查询鲨鱼达到目标体重所需的最少吃鱼数量。

关键规则：

• 鲨鱼只能吃体重严格小于自己当前体重的鱼
• 吃鱼后鲨鱼体重增加该鱼的体重
• 需要处理动态的鱼群变化

解题思路

核心观察

1. 贪心策略：鲨鱼应该尽可能吃它能吃的最大的鱼，这样增长最快
2. 数据结构需求：需要高效支持：
   • 插入/删除鱼
   • 查询小于某个重量的所有鱼
   • 按重量顺序访问鱼

算法设计

代码采用了线段树 + 离散化 + 贪心模拟的方法：

主要组件：

1. 离散化：将所有鱼的重量映射到紧凑的索引
2. 线段树：维护每个重量区间内鱼的总重量和数量
3. 贪心模拟：反复吃当前能吃的最大鱼，直到达到目标

代码详解

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

const int N = 4e5 + 1e3 + 7;

int n, q;

// 线段树节点
struct T {
    int l, r, ls, rs;
    int sum, cnt;  // 总重量和鱼的数量
} t[N * 2 + 1];

void update(int x) {
    t[x].sum = t[t[x].ls].sum + t[t[x].rs].sum;
    t[x].cnt = t[t[x].ls].cnt + t[t[x].rs].cnt;
}

int cnt;

// 构建线段树
int build(int l, int r) {
    int x = ++cnt;
    t[x].l = l, t[x].r = r;
    
    if (l == r) {
        t[x].sum = t[x].cnt = 0;
        return x;
    }
    
    int mid = (t[x].l + t[x].r) >> 1;
    t[x].ls = build(l, mid);
    t[x].rs = build(mid + 1, r);
    update(x);
    return x;
}

// 修改线段树
void change(int x, int l, int r, int vs, int vc) {
    if (t[x].l == l && t[x].r == r) {
        t[x].sum = vs;
        t[x].cnt = vc;
        return;
    }
    
    int mid = (t[x].l + t[x].r) >> 1;
    if (l <= mid)
        change(t[x].ls, l, r, vs, vc);
    else
        change(t[x].rs, l, r, vs, vc);
    update(x);
}

vector<array<int, 4>> E;  // 记录临时吃掉的鱼

// 核心函数：从A吃到至少B
int eat(int x, int l, int r, int &A, int B) {
    if (l <= t[x].l && t[x].r <= r) {
        if (A >= B || !t[x].sum) return 0;
        
        // 如果整个区间都能吃掉
        if (A + t[x].sum < B || t[x].l == t[x].r) {
            A += t[x].sum;
            int ret = t[x].cnt;
            // 记录吃掉的鱼，用于回滚
            E.push_back({t[x].l, t[x].r, t[x].sum, t[x].cnt});
            t[x].sum = 0;
            t[x].cnt = 0;
            return ret;
        }
    }
    
    int mid = (t[x].l + t[x].r) >> 1;
    int ret = 0;
    
    // 先吃右子树（更大的鱼）
    if (r > mid)
        ret += eat(t[x].rs, l, r, A, B);
    if (l <= mid)
        ret += eat(t[x].ls, l, r, A, B);
    
    update(x);
    return ret;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    cin >> n;
    vector<int> X;  // 所有鱼的重量（用于离散化）
    vector<array<int, 3>> qrs;  // 存储所有操作
    
    // 读入初始小鱼
    for (int i = 1; i <= n; i++) {
        int w;
        cin >> w;
        X.push_back(w);
        qrs.push_back({2, w, 0});  // 添加鱼操作
    }
    
    cin >> q;
    // 读入所有操作
    for (int i = 1; i <= q; i++) {
        int o;
        cin >> o;
        if (o == 1) {
            int s, t;
            cin >> s >> t;
            qrs.push_back({o, s, t});
        } else if (o == 2) {
            int w;
            cin >> w;
            X.push_back(w);
            qrs.push_back({o, w, 0});
        } else {
            int w;
            cin >> w;
            qrs.push_back({o, w, 0});
        }
    }
    
    // 离散化
    sort(X.begin(), X.end());
    X.erase(unique(X.begin(), X.end()), X.end());
    
    build(0, (int)X.size() - 1);
    
    // 管理每个重量级别的鱼的数量
    vector<int> l(X.size()), r(X.size(), -1);
    multiset<int> s;  // 维护当前所有鱼的重量
    
    // 处理所有操作
    for (auto [o, a, b] : qrs) {
        if (o == 2) {  // 添加鱼
            auto p = lower_bound(X.begin(), X.end(), a) - X.begin();
            p += ++r[p];  // 找到该重量的下一个位置
            change(1, p, p, a, 1);
            s.insert(a);
        } else if (o == 3) {  // 删除鱼
            auto p = lower_bound(X.begin(), X.end(), a) - X.begin();
            p += l[p]++;  // 找到该重量的下一个要删除的位置
            change(1, p, p, 0, 0);
            s.erase(s.find(a));
        } else {  // 查询操作
            int ans = 0;
            E.clear();
            int A = a;  // 当前鲨鱼重量
            
            while (A < b) {
                // 找到下一个关键点
                auto it = s.lower_bound(A);
                int B;
                
                if (it == s.end() || *it + 1 > b)
                    B = b;
                else
                    B = *it + 1;
                
                // 计算能吃的最大的鱼的索引范围
                int lim = (int)(lower_bound(X.begin(), X.end(), A) - X.begin()) - 1;
                
                if (lim < 0) break;
                
                // 吃鱼
                ans += eat(1, 0, lim, A, B);
                
                if (A < B) break;
            }
            
            // 回滚：恢复吃掉的鱼
            reverse(E.begin(), E.end());
            for (auto [l, r, s, c] : E)
                change(1, l, r, s, c);
            
            if (A >= b)
                cout << ans << "\n";
            else
                cout << "-1\n";
        }
    }
}

算法原理

贪心策略

鲨鱼总是吃当前能吃的最大的鱼，因为：

• 吃大鱼能更快增加体重
• 吃大鱼后可能解锁更多的大鱼可吃

线段树的作用

1. 高效查询：快速找到小于某个重量的所有鱼
2. 区间统计：维护每个重量区间的总重量和鱼数量
3. 动态更新：支持鱼的添加和删除

关键函数 eat

这个函数实现了贪心吃鱼的过程：

1. 从当前能吃的最大鱼开始吃
2. 如果整个区间都能吃掉，就一次性吃掉
3. 否则递归处理左右子树
4. 记录吃掉的鱼用于回滚（因为查询操作不应该实际改变鱼群）

复杂度分析

• 时间复杂度：每个查询操作 $O(\log^2 n)$（线段树深度 × 贪心轮数）
• 空间复杂度：$O(n)$ 存储线段树和鱼群信息

样例解析

对于样例中的查询 1 2 3：

• 初始鲨鱼重量 2，目标 3
• 能吃重量为 1 的鱼
• 吃1条鱼后重量变为 3，达到目标

对于查询 1 2 5：

• 初始重量 2，目标 5
• 先吃重量1的鱼 → 重量3
• 再吃重量1的鱼 → 重量4
• 无法继续（没有小于4的鱼），输出-1

总结

这道题的解题亮点：

1. 贪心+数据结构：结合贪心策略和线段树高效模拟
2. 离散化处理：处理大范围权重值
3. 查询回滚：查询操作不实际改变鱼群状态
4. 多操作支持：统一处理添加、删除和查询

这种"贪心模拟+数据结构优化"的方法在解决这类动态优化问题时非常有效。