bzoj1707[Usaco2007 Nov]tanning分配防晒霜*

bzoj1707[Usaco2007 Nov]tanning分配防晒霜

题意：

n头牛，第i头适应spf值在ai到bi之间的防晒霜。m种防晒霜，每种spf值为ci，有di瓶，问最多多少奶牛能得到合适的防晒霜。n，m≤2500。

题解：

贪心，把牛按上限从小到大排序，然后对于每只奶牛，应该选它可以用的spf值最低的防晒霜。这个过程可以用set维护。

代码：

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 #include <set>
 5 #define inc(i,j,k) for(int i=j;i<=k;i++)
 6 #define maxn 2510
 7 #define INF 0x3fffffff
 8 using namespace std;
 9 
10 inline int read(){
11     char ch=getchar(); int f=1,x=0;
12     while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar();}
13     while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
14     return f*x;
15 }
16 struct nd{int l,r; bool operator < (const nd &a)const{return r==a.r?l<a.l:r<a.r;}}nds[maxn];
17 multiset<nd>st; int c,l,ans;
18 int main(){
19     c=read(); l=read(); inc(i,1,c)nds[i].l=read(),nds[i].r=read(); sort(nds+1,nds+1+c);
20     inc(i,1,l){int x=read(),y=read(); st.insert((nd){y,x});} st.insert((nd){0,INF});
21     inc(i,1,c){
22         multiset<nd>::iterator sti=st.lower_bound((nd){0,nds[i].l}); if(sti->r>nds[i].r)continue;
23         int x=sti->l,y=sti->r; st.erase(sti); x--; if(x)st.insert((nd){x,y}); ans++;
24     }
25     printf("%d",ans); return 0;
26 }

20160926