题目地址:http://poj.org/problem?id=3614

题目大意

有$C$个奶牛去晒太阳 ($1 \leq C \leq 2500$),每个奶牛各自能够忍受的阳光强度有一个最小值$minSPF$和一个最大值$maxSPF$,太大就晒伤了,太小奶牛没感觉。

而刚开始的阳光的强度非常大,奶牛都承受不住,然后奶牛就得涂抹防晒霜,防晒霜的作用是让阳光照在身上的阳光强度固定为某个值$SPF$。

那么为了不让奶牛烫伤,又不会没有效果。

给出了$L$种防晒霜。每种的数量$cover$和固定的阳光强度$SPF$也给出来了

每个奶牛只能抹一瓶防晒霜,最后问能够享受晒太阳的奶牛有几个。

思路

贪心题,首先按照各个奶牛的$minSPF$由小到大排列,各个防晒霜的$SPF$也是从小到大排列。

然后$SPF$从小到大取,满足的奶牛的$maxSPF$入队,最小堆取出每次的最小的$maxSPF$,若能用防晒霜则用,不能则舍弃改奶牛。

AC代码

/*************************************************************************
    > File Name: 3614.cpp
      > Author: Netcan
      > Blog: http://www.netcan.xyz
      > Mail: 1469709759@qq.com
      > Created Time: 2015-10-24 六 16:13:53 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

int C, L;
typedef pair<int, int> P;
P cows[2502], bots[2502]; // 羊, first->minspf, second->maxspf, 防晒瓶first->spf, second->covers

void solve() {
    sort(cows, cows+C);
    sort(bots, bots+L);
    priority_queue<int, vector<int>, greater<int> > que; // maxspf的最小堆
    int ans = 0;
    int j = 0;
    // for(int i=1; i<C; ++i) cout << cows[i].first << cows[i].second << endl;
    // for(int i=0; i<L; ++i) cout << bots[i].first << bots[i].second << endl;

    for(int i=0; i<L; ++i) {
        while(j<C && cows[j].first <= bots[i].first) {
            que.push(cows[j].second); // minspf小于当前防晒霜的maxspf的最小堆
            ++j;
        }

        while(!que.empty() && bots[i].second > 0) {
            if(que.top() >= bots[i].first) {
                --bots[i].second;
                ++ans;
            }
            que.pop(); // 去掉,若无法满足条件也去掉,因为后面的防晒霜spf更大,更加不满足
        }
    }
    cout << ans << endl;
}

int main()
{
#ifdef Oj
    freopen("3614.in", "r", stdin);
#endif
    cin >> C >> L;
    for(int i=0; i<C; ++i) cin >> cows[i].first >> cows[i].second;
    for(int i=0; i<L; ++i) cin >> bots[i].first >> bots[i].second;
    solve();
    return 0;
}