防晒

AcWing-110-防晒

分析

见《进阶指南》第42页。

实现

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 2510;
struct Cow {
    int min_spf, max_spf;
    bool operator < (const Cow& o) const {
        if (min_spf == o.min_spf)
            return max_spf > o.max_spf;
        return min_spf > o.min_spf;
    }
};
struct Cream {
    int spf, total;
    bool operator < (const Cream& o) const {
        return spf > o.spf;
    }
};
int C, L;
Cow cow[N];
Cream cream[N];

int main () {
    scanf("%d%d", &C, &L);
    for (int i = 1; i <= C; ++ i) scanf("%d%d", &cow[i].min_spf, &cow[i].max_spf);
    for (int i = 1; i <= L; ++ i) scanf("%d%d", &cream[i].spf, &cream[i].total);

    sort(cow + 1, cow + C + 1);
    sort(cream + 1, cream + L + 1);
    int res = 0;
    for (int i = 1; i <= C; ++ i) {
        int min_spf = cow[i].min_spf, max_spf = cow[i].max_spf;
        for (int j = 1; j <= L; ++ j) {
            int spf = cream[j].spf;
            if (min_spf <= spf && spf <= max_spf
                && cream[j].total > 0
            ) {
                ++ res;
                -- cream[j].total;
                break;
            }
        }
    }
    printf("%d", res);
    return 0;
}