按右端点升序贪心处理请求，只要整段畜栏最小剩余容量仍大于零就接下，并用线段树维护区间最小值。
OJ: luogu
题目 ID: P1937
难度:提高+/省选-
标签:贪心线段树区间最小值区间加建模
日期: 2026-06-21 02:58
题意
有 N 个畜栏，第 i 个畜栏容量是 C_i。
每个请求 [l, r] 表示：如果想满足这头牛，就必须在区间 [l, r] 中的每一个畜栏都给它预留 1 单位容量。
问最多能满足多少个请求。
思路
先看一个可以直接验证想法的朴素解：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 30;
struct Request {
int l, r;
};
int n, m;
int cap[MAXN];
int remain_cap[MAXN];
Request req[MAXN];
int best_ans;
bool can_take(int idx) {
for (int i = req[idx].l; i <= req[idx].r; i++) {
if (remain_cap[i] == 0) {
return false;
}
}
return true;
}
void apply_req(int idx, int delta) {
for (int i = req[idx].l; i <= req[idx].r; i++) {
remain_cap[i] += delta;
}
}
void dfs(int idx, int chosen) {
if (idx > m) {
best_ans = max(best_ans, chosen);
return;
}
if (chosen + (m - idx + 1) <= best_ans) {
return;
}
if (can_take(idx)) {
apply_req(idx, -1);
dfs(idx + 1, chosen + 1);
apply_req(idx, 1);
}
dfs(idx + 1, chosen);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
// 这是一个小数据精确暴力：
// 枚举每个请求接不接，并维护每个畜栏的剩余容量。
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> cap[i];
remain_cap[i] = cap[i];
}
for (int i = 1; i <= m; i++) {
cin >> req[i].l >> req[i].r;
}
dfs(1, 0);
cout << best_ans << '\n';
return 0;
}brute.cpp 直接枚举每个请求接不接，并维护每个畜栏当前剩余多少容量。
它是精确解，但只能处理很小的数据。
这题的关键是一个区间贪心。
把请求按右端点从小到大排序。 如果右端点相同，就按左端点从大到小排序。
这样做的原因是：
- 结束更早的请求更应该优先保留
- 同样结束在一个位置时，更短的区间更不容易浪费左边额外的位置容量
顺序固定后，处理当前请求 [l, r] 时就只有一个判断：
- 区间
[l, r]上的每个畜栏是否都还有至少1单位容量
这等价于：
- 查询
[l, r]上的最小剩余容量是否大于0
如果可以接，就把整段区间剩余容量都减 1。
于是问题变成标准的两件事：
- 区间最小值查询
- 区间整体加法修改
用懒标记线段树维护即可。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000 + 5;
const int INF = 0x3f3f3f3f;
struct Request {
int l, r;
};
int n, m;
int cap[MAXN];
Request req[MAXN];
int seg_min[MAXN << 2];
int lazy_add[MAXN << 2];
bool cmp_req(const Request &a, const Request &b) {
if (a.r != b.r) {
return a.r < b.r;
}
return a.l > b.l;
}
void push_up(int u) {
seg_min[u] = min(seg_min[u << 1], seg_min[u << 1 | 1]);
}
void build(int u, int l, int r) {
lazy_add[u] = 0;
if (l == r) {
seg_min[u] = cap[l];
return;
}
int mid = (l + r) >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
push_up(u);
}
void apply_add(int u, int val) {
seg_min[u] += val;
lazy_add[u] += val;
}
void push_down(int u) {
if (lazy_add[u] == 0) {
return;
}
apply_add(u << 1, lazy_add[u]);
apply_add(u << 1 | 1, lazy_add[u]);
lazy_add[u] = 0;
}
void range_add(int u, int l, int r, int ql, int qr, int val) {
if (ql <= l && r <= qr) {
apply_add(u, val);
return;
}
push_down(u);
int mid = (l + r) >> 1;
if (ql <= mid) {
range_add(u << 1, l, mid, ql, qr, val);
}
if (qr > mid) {
range_add(u << 1 | 1, mid + 1, r, ql, qr, val);
}
push_up(u);
}
int query_min(int u, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) {
return seg_min[u];
}
push_down(u);
int mid = (l + r) >> 1;
int ans = INF;
if (ql <= mid) {
ans = min(ans, query_min(u << 1, l, mid, ql, qr));
}
if (qr > mid) {
ans = min(ans, query_min(u << 1 | 1, mid + 1, r, ql, qr));
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> cap[i];
}
for (int i = 1; i <= m; i++) {
cin >> req[i].l >> req[i].r;
}
sort(req + 1, req + m + 1, cmp_req);
build(1, 1, n);
int ans = 0;
for (int i = 1; i <= m; i++) {
// 若整段区间的最小剩余容量还大于 0，
// 说明这头牛的请求还能整体接下。
if (query_min(1, 1, n, req[i].l, req[i].r) > 0) {
ans++;
range_add(1, 1, n, req[i].l, req[i].r, -1);
}
}
cout << ans << '\n';
return 0;
}复杂度
排序复杂度是
每个请求需要一次区间最小值查询和最多一次区间加法修改，所以总时间复杂度是
总结
这题最核心的点有两个：
- 把“能否接请求”转成“区间最小剩余容量是否大于
0” - 按右端点升序做区间贪心
剩下就是用线段树把区间最小值和整段减 1 维护起来。