Sunscreen
Time Limit: 1000MS |
Memory Limit: 65536K |
Total Submissions: 10586 |
Accepted: 3702 |
Description
To avoid unsightly burns while tanning, each of the C (1 ≤ C ≤ 2500) cows must cover her hide withsunscreen 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 sufferssunburn; if the SPF rating is too high, the cow doesn'ttan 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 lotionfrom only one bottle.
What is the maximum number of cows that can protect themselveswhile 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 twointegers: minSPFi and maxSPFi
* Lines C+2..C+L+1:Line i+C+1describes 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 cowsthat can be protected while tanning
SampleInput
3 2
3 10
2 5
1 5
6 2
4 1
SampleOutput
2
Source
USACO 2007 November Gold
算法分析:
题意:n个母牛要抹上防晒物品,对防晒物品有系数要求,,给出若干种防晒品的防晒系数和数量,问最多多少奶牛能使用防晒物品。
分析:
牛按最小值升序排序,物品按系数升序排序。维护一个牛最大程度的优先队列,选取规则为最小程度小于当前物品的系数,然后优先对列出队,是否可以选择物品。
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<cmath>
#include<iostream>
#include<sstream>
#include<iterator>
#include<algorithm>
#include<string>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<deque>
#include<queue>
#include<list>
using namespace std;
const double eps = 1e-8;
typedef long long LL;
typedef unsigned long long ULL;
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const LL LL_INF = 0x3f3f3f3f3f3f3f3f;
const LL LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MOD = 1e9 + 7;
const double pi = acos(-1.0);
const int MAXN = 1e5 + 10;
const int MAXT = 10000 + 10;
#define N 2550
struct node
{int x,y;
}cow[N],l[N];int n,m;
bool cmp(const node&a,const node&b)
{ return a.x<b.x;}
int solve()
{sort(cow+1,cow+n+1,cmp);sort(l+1,l+m+1,cmp);priority_queue<int,vector<int>,greater<int> >q;//从小到大牌排列,默认是从大到小 int ans=0,cur=1;for(int i=1;i<=m;i++){while(cur<=n&&cow[cur].x<=l[i].x){q.push(cow[cur].y); //母牛进队++cur; //进队母牛+1}while(!q.empty()&&l[i].y){int t=q.top();q.pop(); if(t>=l[i].x){ans++; //可以使用--l[i].y; //物品数量-1}}}return ans;
}
int main()
{while(scanf("%d%d",&n,&m)!=EOF){for(int i=1;i<=n;i++){scanf("%d%d",&cow[i].x,&cow[i].y);}for(int i=1;i<=m;i++){scanf("%d%d",&l[i].x,&l[i].y);}printf("%d\n",solve());}return 0;}