POJ3614 Sunscreen

POJ3614 Sunscreen

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 ≤ minSPFi ≤ 1,000; minSPFimaxSPFi ≤ 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?

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: 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

Output

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

Sample Input

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

Sample Output

1
2

Answer

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <cstdio> 
#include <algorithm>
#include <queue>
using namespace std;

typedef pair<int, int> tmp;
tmp cows[2550], bottles[2550];

priority_queue<int, vector<int>, greater<int> > pq;

int main() {
int c, l;
scanf("%d %d", &c, &l);
for (int i = 0; i < c; ++i)
scanf("%d %d", &cows[i].first, &cows[i].second);
for (int i = 0; i < l; ++i)
scanf("%d %d", &bottles[i].first, &bottles[i].second);

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

int j = 0, ans = 0;
for (int i = 0; i < l; ++i) {
while (j < c && cows[j].first <= bottles[i].first) {
pq.push(cows[j++].second);
}
while (!pq.empty() && bottles[i].second > 0) {
int tmp = pq.top();
pq.pop();
if (tmp >= bottles[i].first) {
++ans;
--bottles[i].second;
}
}
}
printf("%d\n", ans);
return 0;
}

Analysis

  1. 每只奶牛有自己的有效防晒区间,给出多种不同数量的防晒霜,求最多可以让多少只奶牛成功防晒。
  2. 将区间按左端点升序排序,将防晒霜按防晒指数升序排序。对于每种防晒霜,将区间左端点不超过它的牛加入最小堆,每次从堆头贪心。
# POJ

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×