题意概括

给定 个畜栏（编号 ），第 个畜栏容量为 。给定 个请求，第 个请求需占用 连续区间。 求在满足所有选中请求不超出任意畜栏容量的前提下，最多能满足的请求数量。 数据范围：。

思路分析

你的代码尝试使用堆（Priority Queue）进行贪心，方向上接近“后悔贪心”或“扫描线”思想，但存在逻辑断层。仅对请求排序并循环无法处理每个位置的容量限制。

数学建模与修正： 本题等价于在数轴 上进行扫描。

1. 扫描线变量：以位置 从 到 推进。
2. 事件处理：

• 入选：当扫描到位置 时，所有以 为起点的请求 加入候选集合。
• 过期：集合中所有右端点 的请求已结束，自动离开集合（释放容量）。
• 冲突解决（核心贪心）：若当前集合大小 ，说明容量不足。根据贪心策略，应丢弃右端点 最大的请求。
• 证明：在当前位置 发生冲突，必须丢弃一个。选择 最大的请求丢弃，等价于移除了一个“占用资源时间最长”的阻碍，从而最大化后续 容纳更多短请求的概率（局部最优导致全局最优）。

数据结构选择： 你需要一个数据结构支持：

1. 插入元素。
2. 删除小于 的元素（过期）。
3. 删除最大元素（溢出丢弃）。 标准 priority_queue 只能高效处理一端的最值。同时支持删除最小值和最大值，需要使用 std::multiset（红黑树），它在 时间内支持双端操作。

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

const int N = 100005;

int n, m;
int c[N];
struct Node {
    int l, r;
} a[N];

bool cmp(Node x, Node y) {
    return x.l < y.l;
}

multiset<int> s;

signed main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    cin >> n >> m;
    for(int i = 1; i <= n; i++) {
        cin >> c[i];
    }
    for(int i = 1; i <= m; i++) {
        cin >> a[i].l >> a[i].r;
    }

    sort(a + 1, a + m + 1, cmp);

    int p = 1; 
    int ans = m; 

    for(int i = 1; i <= n; i++) {
        while(p <= m && a[p].l == i) {
            s.insert(a[p].r);
            p++;
        }

        while(!s.empty() && *s.begin() < i) {
            s.erase(s.begin());
        }

        while(s.size() > c[i]) {
            s.erase(prev(s.end()));
            ans--;
        }
    }

    cout << ans << endl;

    return 0;
}

代码逻辑解释

1. 排序：将请求按左端点 升序排序，以便配合扫描线 逐个加入。
2. **扫描 **：

• s.insert(a[p].r)：将所有在当前位置 开始的请求加入集合。
• s.erase(s.begin())：移除所有右端点小于 的请求（已完成任务，不占用 ）。
• s.erase(prev(s.end()))：若当前请求数超过 ，贪心移除右端点最远的请求（最“占地”的），并将总答案减一。

3. 答案：初始假设 个全选，每次因容量不足丢弃时减一。

复杂度

• 时间复杂度：。排序耗时 ，每个请求最多进出 multiset 一次，每次操作 。
• 空间复杂度：，用于存储数组和集合。

https://www.luogu.com.cn/problem/P1937