poj 3614 Sunscreen

Sunscreen

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 9014		Accepted: 3164

Description

To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide with sunscreen when they're at the beach. Cow i has a minimum and maximum SPF rating (1 ≤ minSPF_i ≤ 1,000; minSPF_i ≤ maxSPF_i ≤ 1,000) that will work. If the SPF rating is too low, the cow suffers sunburn; if the SPF rating is too high, the cow doesn't tan at all........

The cows have a picnic basket with L (1 ≤ L ≤ 2500) bottles of sunscreen lotion, each bottle i with an SPF rating SPF_i (1 ≤ SPF_i ≤ 1,000). Lotion bottle i can cover cover_i cows with lotion. A cow may lotion from only one bottle.

What is the maximum number of cows that can protect themselves while tanning given the available lotions?

Input

* Line 1: Two space-separated integers: C and L
* Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPF_i and maxSPF_i 
* Lines C+2..C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPF_i and cover_i

Output

A single line with an integer that is the maximum number of cows that can be protected while tanning

Sample Input

3 2
3 10
2 5
1 5
6 2
4 1

Sample Output

2

/*
* @Author: Lyucheng
* @Date:   2017-07-19 15:00:45
* @Last Modified by:   Lyucheng
* @Last Modified time: 2017-07-19 17:16:39
*/
/*
 题意：有C个奶牛在晒太阳，每个奶牛能承受阳光强的有一个min和max，如果小了，就会晒伤，如果大了就晒不到了，然后又L瓶防晒霜
    每种防晒霜能将阳光集中到一个强度上，并且有一定数量（这个一开始没翻译出来，还以为每个防晒霜只能给i号奶牛用，问你最多
    有多少头奶牛可以在舒服的环境中晒太阳
 思路：贪心，奶牛按照max从小到大，然后每只奶牛用剩余防晒中最小的

*/
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <string>
#include <math.h>
#include <stdlib.h>
#include <time.h>

#define MAXN 2505

using namespace std;

struct Cow{
    int mi,ma;
    bool operator < ( const Cow & other) const{
        return ma<other.ma;
    }
}cow[MAXN];
struct Node{
    int pos,num;
    bool operator < ( const Node & other) const{
        return pos<other.pos;
    }
}node[MAXN];
int c,l;
int x,y;

int main(){ 
    // freopen("in.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    while(scanf("%d%d",&c,&l)!=EOF){
        for(int i=0;i<c;i++){
            scanf("%d%d",&cow[i].mi,&cow[i].ma);
        }

        sort(cow,cow+c);
        
        for(int i=0;i<l;i++){
            scanf("%d%d",&node[i].pos,&node[i].num);
            
        }

        sort(node,node+l);
        int res=0;
        for(int i=0;i<c;i++){
            for(int j=0;j<l;j++){
                if(node[j].num>0&&node[j].pos>=cow[i].mi&&node[j].pos<=cow[i].ma){
                    node[j].num--;
                    res++;
                    break;
                }
            }
        }
        printf("%d
",res);
    }
    return 0;
}