poj3614-贪心、优先队列

时间：2022-12-01 17:40:18
Language:
Sunscreen
Time Limit: 1000MS   Memory Limit: 65536K
Total Submissions: 2754   Accepted: 958

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 SPFrating 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 2
3 10
2 5
1 5
6 2
4 1

Sample Output

2

1.贪心
奶牛按可以承受的最大值从小到大排序，lotion也从小到大排序。

#include<iostream>
#include<set>
#include<map>
#include<vector>
#include<queue>
#include<cmath>
#include<climits>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
typedef long long LL;
using namespace std;
struct node
{
    int maxspf;
    int minspf;
    friend bool operator<(const node &a,const node &b)
    {
        return a.maxspf<b.maxspf;
    }
} cow[2505];
struct node1
{
    int num,sun;
    friend bool operator<(const node1 &a,const node1 &b)
    {

        return a.sun<b.sun;
    }
} a[2505];
int main()
{
    
    int C,L;
    while(cin>>C>>L)
    {
        for(int i=0; i<C; i++)
            cin>>cow[i].minspf>>cow[i].maxspf;
        for(int i=0; i<L; i++)
            cin>>a[i].sun>>a[i].num;
        sort(cow,cow+C);
        sort(a,a+L);
       
        int ans=0,j=0,i=0;
       
        for(int i=0; i<C; i++)
        {
            for(int j=0; j<L; j++)
            {
                if(cow[i].minspf<=a[j].sun&&cow[i].maxspf>=a[j].sun&&a[j].num>0)
                {
                    ans++;
                    a[j].num--;
                    break;
                }
                if(a[j].sun>cow[i].maxspf)
                    break;
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

2.优先队列。
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <map>
#include <vector>
#include <queue>
#define MAXN 2555
#define INF 1000000007
using namespace std;
int C, L;
typedef pair<int, int> P;
priority_queue<int, vector<int>, greater<int> > q;
P cow[MAXN], bot[MAXN];
int main()
{
    scanf("%d%d", &C, &L);
    for(int i = 0; i < C; i++) scanf("%d%d", &cow[i].first, &cow[i].second);
    for(int i = 0; i < L; i++) scanf("%d%d", &bot[i].first, &bot[i].second);
    sort(cow, cow + C);
    sort(bot, bot + L);
    int j = 0, ans = 0;
    for(int i = 0; i < L; i++)
    {
        while(j < C && cow[j].first <= bot[i].first)
        {
            q.push(cow[j].second);
            j++;
        }
        while(!q.empty() && bot[i].second)
        {
            int x = q.top();
            q.pop();
            if(x < bot[i].first) continue;
            ans++;
            bot[i].second--;
        }
    }
    printf("%d\n", ans);
    return 0;
}
标签：

相关文章