题目描述
有 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
使用贪心即可解决。
将奶牛的阳光需求度按“最小”阳光需求度从大到小排序,将防晒霜的固定阳光强度按从大到小排序,
因为当目前防晒霜的固定阳光强度也无法满足该奶牛的最小阳光需求强度,证明之后的防晒霜也无法满足
因此复杂度为O(n2)
设任意两瓶防晒霜为a1, a2,对于固定防晒度大小的关系为,a1 < a2,那对于后面的奶牛来说就有这三种情况:
1.a1和a2均可使用
2.a2能用a1不可用
3.两者均不可用。
很显然,我们先选择固定防晒度较大的a2对问题的整体影响更大。
算法
$O(n^2)$
C++ 代码
#include<bits/stdc++.h>
using namespace std;
使用贪心即可解决。
将奶牛的阳光需求度按“最小”阳光需求度从大到小排序,将防晒霜的固定阳光强度按从大到小排序,
因为当目前防晒霜的固定阳光强度也无法满足该奶牛的最小阳光需求强度,证明之后的防晒霜也无法满足
因此复杂度为O(n2)
设任意两瓶防晒霜为a1, a2,对于固定防晒度大小的关系为,a1 < a2,那对于后面的奶牛来说就有这三种情况:
1.a1和a2均可使用
2.a2能用a1不可用
3.两者均不可用。
很显然,我们先选择固定防晒度较大的a2对问题的整体影响更大。
struct Node
{
int l;//最小阳光需求度
int r;//最大阳光需求度
}a[2505];
struct bt
{
int p;//固定阳光强度
int tot;//瓶数
}b[2505];
int ans;//共有多少只奶牛可以满足晒太阳
bool cmp1(Node x,Node y)
{
return x.l>y.l;//按最小阳光的强度从大到小排序
}
bool cmp2(bt x,bt y)
{
return x.p>y.p;//按固定阳光强度从大到小排序
}
int main()
{
int c,l;
cin>>c>>l;//c只奶牛,l种防晒霜
for(int i=1;i<=c;i++)
{
cin>>a[i].l>>a[i].r;
}
for(int i=1;i<=l;i++)
{
cin>>b[i].p>>b[i].tot;
}
sort(a+1,a+c+1,cmp1);
sort(b+1,b+l+1,cmp2);
/*for(int i=1;i<=c;i++)
{
cout<<a[i].l<<" "<<a[i].r<<endl;
}*/
for(int i=1;i<=c;i++)
{
for(int j=1;j<=l;j++)
{
if(a[i].l<=b[j].p&&a[i].r>=b[j].p&&b[j].tot!=0)
{//当目前的防晒霜满足该奶牛的最小阳光强度,选择该防晒霜。
//该题有一点,即固定阳光强度最大的防晒霜给最小阳光强度最大的使用
b[j].tot--;
ans++;
break;
}
}
}
cout<<ans<<endl;
return 0;
}