题目链接

Sunscreen POJ - 3614

思路

$$ \begin{aligned}先排序，对于种防晒霜，类似尺取法把牛处理好（先push后pop），然后从小根堆中取值。\end{aligned} $$

时间复杂度

$$ O(Nlog(N)) $$

代码

#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int MAXN = 2500 + 10;

pair<int, int> cows[MAXN];
pair<int, int> lotons[MAXN];

int main() {
    int c, l;
    scanf("%d%d", &c, &l);// don't forget &
    for (int i = 1; i <= c; i++) {
        scanf("%d%d", &cows[i].first, &cows[i].second);// don't forget &
    }
    for (int i = 1; i <= l; i++) {
        scanf("%d%d", &lotons[i].first, &lotons[i].second);// don't forget &
    }
    sort(cows + 1, cows + 1 + c);
    sort(lotons + 1, lotons + 1 + l);

    int ans = 0;
    priority_queue<int, vector<int>, greater<int> > sm;
    int cur = 1;
    for (int i = 1; i <= l; i++) {
        while (cur <= c && cows[cur].first <= lotons[i].first) {
            sm.push(cows[cur].second);
            cur++;
        }
        while (sm.size() != 0 && sm.top() < lotons[i].first) {
            sm.pop();
        }
        while (lotons[i].second != 0 && sm.size() != 0) {
            lotons[i].second--;
            ans++;
            sm.pop();
        }
    }
    printf("%d", ans);

    return 0;
}