一、内容
C (1 ≤ C ≤ 2500) 头奶牛在海滩边晒太阳，要避免在日光浴时产生难看的灼伤，每头奶牛必须用防晒霜覆盖它的皮肤。第 i 头奶牛有一个最小和最大 SPF 值 (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) 将会起作用。如果 SPF 值太低，则奶牛会受到日光灼伤；如果 SPF 值太高，则牛奶无法进行日光浴。
奶牛们有一个野餐篮子，带了 L (1 ≤ L ≤ 2500) 瓶防晒霜乳液，第 i 瓶的 SPF 值是 SPFi (1 ≤ SPFi ≤ 1,000) 。第 i 瓶防晒霜可以涂抹覆盖 coveri 头奶牛。一头牛奶只能用一瓶防晒霜涂抹。
对于给定的防晒霜乳液，最多可以有多少头奶牛能够在日光浴时避免被灼伤？
输入
第 1 行: 两个以空格分隔的整数: C 和 L
第 2 到 C+1 行: 第 i 行描述了第 i 头奶牛的防晒霜约束条件，包括两个整数: minSPFi 和 maxSPFi
第 C+2 到 C+L+1 行: 第 i+C+1 行描述了第 i 个防晒霜瓶，包括以空格分隔的整数: SPFi 和 coveri
输出
只包含一个整数的单行，表示日光浴时受到防晒保护的奶牛的最大数量。
示例输入
3 2
3 10
2 5
1 5
6 2
4 1
示例输出
2
二、思路
按照minSPF递减进行排列，所以当选择一个不低于当前奶牛的minSPF的防晒霜时，那么它比然大于后面的SPF。当我们有2瓶x,y防晒霜，SPF[X] < SPF[Y]那么下面的牛对2瓶防晒霜的使用情况为： 1.x能用，y能用。 2.x能用 y不能用。 3.x,y都不能用故我们尽量选择SPF大的防晒霜进行使用。然后当minSPF相同的两头牛比较时，我们应先满足maxSPF大的牛，道理同理上面。故maxSPF按第二关键从递减排序。虽然这影响不大，因为包含在1,2种情况结果都一样。
三、代码
#include <cstdio>
#include <algorithm>
#include <iostream>
using namespace std
;
const int N
= 2505;
struct Niu
{
int minS
, maxS
;
friend bool operator < (Niu a
, Niu b
) {
if (a
.minS
== b
.minS
) return a
.maxS
> b
.maxS
;
return a
.minS
> b
.minS
;
}
} niu
[N
];
struct Lotion
{
int spf
, num
;
friend bool operator < (Lotion a
, Lotion b
){
return a
.spf
< b
.spf
;
}
} lot
[N
];
int c
, L
, ans
;
int main() {
scanf("%d%d", &c
, &L
);
for (int i
= 0; i
< c
; i
++) {
scanf("%d%d", &niu
[i
].minS
, &niu
[i
].maxS
);
}
for (int i
= 0; i
< L
; i
++) {
scanf("%d%d", &lot
[i
].spf
, &lot
[i
].num
);
}
sort(niu
, niu
+ c
);
sort(lot
, lot
+ L
);
for (int i
= 0; i
< c
; i
++) {
int max
= -1;
int index
= -1;
for (int j
= 0; j
< L
&& lot
[j
].spf
<= niu
[i
].maxS
; j
++) {
if (lot
[j
].num
&& lot
[j
].spf
>= niu
[i
].minS
&& lot
[j
].spf
>= max
) {
index
= j
;
max
= lot
[j
].spf
;
}
}
if (index
!= -1) {
lot
[index
].num
--;
ans
++;
}
}
printf("%d\n", ans
);
return 0;
}
