题目大意:
给你一些母牛,母牛有能容忍日光浴的最小和最大光照强度。每仅仅母牛能够涂一次SPF,SPF能够将母牛能够承受的光照强度固定在某个地方。如今给你母牛的最小和最大值和不同的spf的光照强度及其数量,求最多能够有多少母牛享受日光浴?
思路:
优先队列。
先按母牛最小承受的排好,然后spf的值也从小到大。
接下来用优先队列(栈顶为最小的)。对于每一个spf,假设一仅仅母牛的最小值小于等于spf则将其最大值入队。(贪心。。如两个母牛一仅仅【1,4】一仅仅【1,5】那么相同情况下选【1,4】不会差于【1,5】)
详见代码。
#include#include #include #include using namespace std;const int MAXN=2500+10;struct cow{ int min,max; bool operator < (const cow& x)const{ return min x.val; }};priority_queue q;int main(){ int c,l; while(~scanf("%d%d",&c,&l)) { while(!q.empty()) q.pop(); for(int i=0;i