题目描述
有C头奶牛进行日光浴,第i头奶牛需要minSPF[i]到maxSPF[i]单位强度之间的阳光。
每头奶牛在日光浴前必须涂防晒霜,防晒霜有L种,涂上第i种之后,身体接收到的阳光强度就会稳定为SPF[i],第i种防晒霜有cover[i]瓶。
求最多可以满足多少头奶牛进行日光浴。
输入格式
第一行输入整数C和L。
接下来的C行,按次序每行输入一头牛的minSPF和maxSPF值,即第i行输入minSPF[i]和maxSPF[i]。
再接下来的L行,按次序每行输入一种防晒霜的SPF和cover值,即第i行输入SPF[i]和cover[i]。
每行的数据之间用空格隔开。
输出格式
输出一个整数,代表最多可以满足奶牛日光浴的奶牛数目。
数据范围
1≤C,L≤2500,
1≤minSPF≤maxSPF≤1000,
1≤SPF≤1000
输入样例
3 2
3 10
2 5
1 5
6 2
4 1
输出样例
2
思路
将奶牛的接收强度从大到小进行排序(排在越前面的l越大)
将防晒霜的spf从大到小进行排序
对于每一头牛,先用spf数值最大的,如果这个防晒霜还有,并且在这头牛的光照强度范围内,则使用,并且防晒霜的数量减一,cnt++,退出并为下一头牛寻找合适的防晒霜,如果不符合则判断下一种防晒霜是否符合要求,直至没有符合的防晒霜
C++ 代码
#include<iostream>
#include<algorithm>
using namespace std;
const int N=2505;
struct node{//每头奶牛可接收的阳光强度范围
int l;//范围最小值
int r;//范围最大值
}a[N];
struct node1{//每瓶防晒霜的spf和数量
int spf;
int cover;//数量
}b[N];
int n,t;
bool cmp(node a,node b){//将奶牛进行排序,按照最小值从小到大进行排序,即最前面的是最靠右的
if(a.l==b.l){//如果最小值相等,则先排最大值大的,即靠右的
return a.r>b.r;
}
return a.l>b.l;
}
bool cmp1(node1 a,node1 b){//将防晒霜进行排序,spf从大到小排序
if(a.spf==b.spf){//如果spf相等,则先排数量多的
return a.cover>b.cover;
}
return a.spf>b.spf;
}
int main()
{
cin >> n >> t;
for(int i=1;i<=n;i++){
cin >> a[i].l >> a[i].r;
}
for(int i=1;i<=t;i++){
cin >> b[i].spf >> b[i].cover;
}
sort(a+1,a+1+n,cmp);//奶牛进行从大到小排序
sort(b+1,b+1+t,cmp1);//防晒霜进行从大到小排序
int cnt=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=t;j++){//每种防晒霜
if(b[j].spf>=a[i].l && b[j].spf<=a[i].r && b[j].cover){//spf符合第i头牛的范围 并且 这种防晒霜还有
b[j].cover--;//防晒霜数量减一
cnt++;//满足条件+1
break;//找到了则第i头牛已经涂了防晒霜,跳出循环,对下一头牛进行操作
}
}
}
cout << cnt << endl;
return 0;
}