首页 > 代码库 > poj 3614 Sunscreen

poj 3614 Sunscreen

2024-08-14 05:23:19   221人阅读

                                                                                                    Sunscreen
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 7450 Accepted: 2627

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

3 23 102 51 56 24 1

Sample Output

2

题意：有C头牛晒太阳，每头牛都有相应的SPF范围，在范围内可以让牛享受太阳，有L瓶防晒霜，每瓶防晒霜都有各自的SPF值，SPF值在某头牛的SPF范围内的防晒霜如果涂在该牛上，可以让该牛享受太阳，问有多少头牛可以享受太阳。
思路：贪心，对于每一种防晒霜，在符合条件的范围内(防晒霜的SPF值大于牛的min_SPF)，每次都筛选出一群牛，将这群牛的max_SPF值压入最小堆，之后尽量用SPF值较小的防晒霜涂于max_SPF较小的牛上。
#define _CRT_SECURE_NO_DEPRECATE#include<iostream>#include<queue>#include<algorithm>#include<functional>//greaterusing namespace std;const int N_MAX = 2500;struct cows {    int low;    int high;    bool operator <(const cows&b)const{        return low<b.low||(low==b.low&&high<b.high);    }};struct  lotion {    int spf;    int num;    bool operator <(const lotion&b)const {        return spf <b.spf ;    }};priority_queue<int,vector<int>,greater<int>>que;//小元素在上cows cow[N_MAX];lotion lo[N_MAX];int main() {    int C, L;    scanf("%d%d",&C,&L);        for (int i = 0;i < C;i++)            scanf("%d%d", &cow[i].low, &cow[i].high);        for (int i = 0;i < L;i++)             scanf("%d%d", &lo[i].spf, &lo[i].num);        sort(cow, cow + C);//按牛的spf最小值从小到大排序        sort(lo, lo + L);//按护肤品的spf值从小到大排        int result=0,cur=0;        for (int i = 0;i < L;i++) {//对于每一种护肤品进行考虑            while (cur<C&&lo[i].spf>=cow[cur].low) {//挑选出满足条件的牛的high值进堆                que.push(cow[cur].high);//进堆后小的high值在上面                cur++;            }            while (que.size() && lo[i].num) {//如果这种护肤品对所有挑选出来的牛都不满足条件，那么只能弃用，因为后面的牛的min值都比护肤品的spf大                int k = que.top();que.pop();                if (k >= lo[i].spf) {//high值小于护肤品的spf值的牛只能不涂，后面的护肤品spf值越来越大更不满足                    result++;                    lo[i].num--;                }            }        }        printf("%d\n",result);        return 0;    }

 

poj 3614 Sunscreen






























        

            
                
                  
                
                

                    联系

                    我们