题目描述
有 C 头奶牛去晒太阳,每头奶牛各自能够忍受的阳光强度有一个最小值和一个最大值,太大就晒伤了,太小奶牛没感觉。而刚开始的阳光的强度非常大,奶牛都承受不住,奶牛得涂抹防晒霜,防晒霜的作用是让阳光照在身上的阳光强度固定为某个值。那么为了不让奶牛烫伤,又不会没有效果。给出了 L 种防晒霜固定的阳光强度和数量,每头奶牛只能抹一瓶防晒霜,求能够享受晒太阳的奶牛最多有几头。
输入
第一行输入两个数 C,L。(1≤C,L≤2500)
接下来 C 行,每行两个数表示每头奶牛能接受的阳光强度的最小值和最大值。(均小于 1000)
再接下来 L 行,每行两个数表示每种防晒霜固定的阳光强度和数量。(均小于 1000)
输出
输出能晒太阳的奶牛的最多数量。
样例输入
3 2
3 10
2 5
1 5
6 2
4 1
样例输出
2
数据规模与约定
时间限制:1 s
内存限制:256 M
100% 的数据保证 1≤C,L≤2500
题意
把问题描述为,对于每个区间,尽可能让更多的点落在区间上,每个区间只能落一个点;
奶牛比作区间,防晒霜比作点。
贪心策略
对于区间a, b;
- 1、若a包含b,则先处理b(小区间) ———–顺序相关
- 2、若a, b区间有交集,则先处理左边界l小的那个 ——— 策略相关
- 3、没有交集,先处理哪个都一样
题解
#include <stdio.h>
#include <algorithm>
using namespace std;
/*
贪心策略:
对于区间a, b;
1、若a包含b,则先处理b(小区间) -----------顺序相关
2、若a, b区间有交集,则先处理左边界l小的那个 --------- 策略相关
3、没有交集,先处理哪个都一样
*/
struct Node {
int l, r; //l表示左边界,r表示右边界
bool operator< (const Node &a) const {
//重载小于号,使其排序的时候满足我们的贪心策略的顺序相关
if (this->l ^ a.l) return this->l > a.l; //左边界不相等时,左边界大的也就是小区间在前面
return this->r < a.r;//左边界相等时,右边界小的也就是小区间在前面
}
};
Node num[2505]; // 奶牛 ( 区间 )
int fs[1000]; //每种防晒值的防晒的防晒霜 ( 点 ) 的数量
int main() {
int c, l, ans = 0;
scanf("%d %d", &c, &l);
for (int i = 1; i <= c; i++) scanf("%d %d", &num[i].l, &num[i].r);
sort(num + 1, num + 1 + c); //处理顺序相关
for (int i = 1, a, b; i <= l; i++) {
scanf("%d %d", &a, &b);
fs[a] += b;
}
for (int i = 1; i <= c; i++) {
//根据顺序相关排序后,处理我们的策略相关
for (int j = num[i].r; j >= num[i].l; j--) {
if (fs[j] == 0) continue;
--fs[j];
++ans;
break;
}
}
printf("%d\n", ans);
return 0;
}