USACO 2007 Nov Gold 3.Sunscreen

2014.12.24 09:46 Wed| 3 visits oi_2015| 2015_刷题日常| Text

Problem

Description

给出n头牛所能接受防晒霜的SPF范围和每瓶防晒霜的SPF值与容量。问最多有多少头牛能够涂上适合它的防晒霜。

Solution

常规贪心就是它了。将每一头牛的范围按照右端点从小到大排序。将防晒霜按照SPF值从小到大排序。然后对于每一头牛选取符合条件的SPF值最小的防晒霜即可。

Code

#include <bits/stdc++.h>
using namespace std;
#define N 2505

int n,c,ans;
multimap<int,int> m;
multimap<int,int>::iterator it;
pair<int,int> p[N];

inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}

int main()
{
    cin>>n>>c;
    for(int i=1;i<=n;i++)
        p[i].second=read(), p[i].first=read();
    sort(p+1,p+n+1);
    for(int x,y,j=1;j<=c;j++)
        x=read(), y=read(),
        m.insert(make_pair(x,y));
    for(int i=1;i<=n;i++)
    {
        it=m.lower_bound(p[i].second);
        if(it==m.end()||it->first>p[i].first) continue;
        if(!--it->second) m.erase(it);
        ans++;
    }
    cout<<ans<<endl;
}