算法题：Sunscreen

问题描述

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≤minSPFi≤1,000; minSPFi≤maxSPFi≤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 SPFi (1≤SPFi≤1,000 ). Lotion bottle i can cover coveri 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?

输入格式

• Line 1: Two space-separated integers: C and L

• Lines 2..C+1: Line i describes cow i's lotion requires with two integers: minSPFi and maxSPFi

• Lines C+2…C+L+1: Line i+C+1 describes a sunscreen lotion bottle i with space-separated integers: SPFi and coveri

输出格式

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

样例

输入

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

输出

2

解决方案

思路

贪心 将Cows的minSPF和Sunscreens的SPF由大到小排序，循环找到的第一瓶Sunscreen就是最合适的。

代码

#include <iostream>
#include <algorithm>

using namespace std;

struct Sunscreen {

    int SPF;
    int count;

    bool operator<(const Sunscreen &obj) const {
        return this->SPF > obj.SPF;
    }

};

struct Cow {
    int minSPF;
    int maxSPF;

    bool operator<(const Cow &obj) const {
        return this->minSPF > obj.minSPF;
    }
};

Cow cows[2505];
Sunscreen sunscreens[2505];

int main() {

    int c, l;
    cin >> c >> l;

    for (int i = 0; i < c; ++i) {
        cin >> cows[i].minSPF >> cows[i].maxSPF;
    }

    for (int i = 0; i < l; ++i) {
        cin >> sunscreens[i].SPF >> sunscreens[i].count;
    }

    sort(cows, cows + c);
    sort(sunscreens, sunscreens + l);

    int ans = 0;
    for (int i = 0; i < c; ++i) {
        for (int j = 0; j < l; ++j) {
            if (sunscreens[j].SPF >= cows[i].minSPF && sunscreens[j].SPF <= cows[i].maxSPF && sunscreens[j].count != 0) {
                --sunscreens[j].count;
                ++ans;
                break;
            }
        }
    }
    cout << ans;

    return 0;
}