傳送門：http://poj.org/problem?id=3614

Sunscreen

Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 10136 Accepted: 3544

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; 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?

Input

• Line 1: Two space-separated integers: C and L
• Lines 2..C+1: Line i describes cow i’s lotion require

---

s 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

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

Sample Output

2

---

解題心得：

題意就是奶牛要去日光浴，奶牛要涂防曬霜，每個奶牛有一個涂防曬霜的區間，每個防曬霜有一個值和數量，問最多可以涂多少只奶牛。

其實面對的最大的問題就是一個奶牛將可以用多個防曬霜，但是它用了其中一個和另一個奶牛產生沖突的防曬霜，所以可以將防曬霜按照值排序，每次取一個出來，將最小值小于這個防曬霜的奶牛都壓入優先隊列（按照終點排序），再從優先隊列中來取。這樣就能先安排好奶終點先結束的奶牛。

---

#include <stdio.h> #include <queue> #include <algorithm> using namespace std;const int maxn = 2510; typedef pair <int,int> P;P cow[maxn],co[maxn]; int n,m;int main() {scanf("%d%d",&n,&m);for(int i=0;i<n;i++)scanf("%d%d",&cow[i].first,&cow[i].second);for(int i=0;i<m;i++)scanf("%d%d",&co[i].first,&co[i].second);sort(cow,cow+n);sort(co,co+m);priority_queue <int, vector<int> , greater <int> > qu;int j = 0,ans = 0;for(int i=0;i<m;i++) {while(j<n && cow[j].first <= co[i].first) {qu.push(cow[j].second);j++;}while(!qu.empty() && co[i].second) {if(qu.top() >= co[i].first) {ans++;co[i].second--;}qu.pop();}}printf("%d\n",ans);return 0; }

轉載于:https://www.cnblogs.com/GoldenFingers/p/9107141.html

總結

以上是生活随笔為你收集整理的POJ ：3614-Sunscreen的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。