题目传送门
【题目大意】
有$C$头奶牛晒日光浴，第$i$头奶牛需要$minSPF[i]$至$maxSPF[i]$之间的日光强度。现在有$L$个防晒霜，第$i$个防晒霜可以使日光强度控制在$SPF[i]$，可以供$cover[i]$头奶牛使用，求最多能满足多少头奶牛。
【思路分析】
其实很容易想到贪心，类似于线段覆盖，把每头奶牛按照$minSPF[i]$的值从小到大排序，把防晒霜也按照$SPF[i]$的值从小到大排序，加一个优先队列，让$maxSPF[i]$小的奶牛先使用防晒霜。
【代码实现】
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 #include<queue> 5 #define rg register 6 #define go(i,a,b) for(rg int i=a;i<=b;i++) 7 using namespace std; 8 const int N=2502; 9 int c,l,ans=0; 10 struct cow{ 11 int min,max; 12 }a[N]; 13 struct lotion{ 14 int SPF,cover; 15 }b[N]; 16 priority_queue< int,vector<int>,greater<int> >q; 17 bool cmpa(cow A,cow B){ 18 if(A.min!=B.min) return A.min<B.min; 19 else return A.max<B.max; 20 } 21 bool cmpb(lotion A,lotion B){ 22 if(A.SPF!=B.SPF) return A.SPF<B.SPF; 23 else return A.cover<B.cover; 24 } 25 int main(){ 26 scanf("%d%d",&c,&l); 27 go(i,1,c) scanf("%d%d",&a[i].min,&a[i].max); 28 go(i,1,l) scanf("%d%d",&b[i].SPF,&b[i].cover); 29 sort(a+1,a+1+c,cmpa);sort(b+1,b+1+l,cmpb); 30 int now=1; 31 go(x,1,l){ 32 while(now<=c && a[now].min<=b[x].SPF)q.push(a[now].max),++now; 33 while(!q.empty() && b[x].cover) 34 { 35 int tmp=q.top();q.pop(); 36 if(b[x].SPF<=tmp)++ans,--b[x].cover; 37 } 38 } 39 printf("%d\n",ans); 40 return 0; 41 } 代码戳这里转载于:https://www.cnblogs.com/THWZF/p/11249325.html
