【POJ - 3614】Sunscreen (优先队列)
Sunscreen
Descriptions
C (1 ≤ C ≤ 2500) 头奶牛在海滩边晒太阳,要避免在日光浴时产生难看的灼伤,每头奶牛必须用防晒霜覆盖它的皮肤。第 i 头奶牛有一个最小和最大 SPF 值 (1 ≤ minSPFi ≤ 1,000; minSPFi ≤ maxSPFi ≤ 1,000) 将会起作用。如果 SPF 值太低,则奶牛会受到日光灼伤;如果 SPF 值太高,则牛奶无法进行日光浴。
奶牛们有一个野餐篮子,带了 L (1 ≤ L ≤ 2500) 瓶防晒霜乳液,第 i 瓶的 SPF 值是 SPFi(1 ≤ SPFi ≤ 1,000) 。第 i 瓶防晒霜可以涂抹覆盖 coveri 头奶牛。一头牛奶只能用一瓶防晒霜涂抹。
对于给定的防晒霜乳液,最多可以有多少头奶牛能够在日光浴时避免被灼伤?
输入
* 第 1 行: 两个以空格分隔的整数: C 和 L
* 第 2 到 C+1 行: 第 i 行描述了第 i 头奶牛的防晒霜约束条件,包括两个整数: minSPFi 和 maxSPFi
* 第 C+2 到 C+L+1 行: 第 i+C+1 行描述了第 i 个防晒霜瓶,包括以空格分隔的整数: SPFi和 coveri
输出
只包含一个整数的单行,表示日光浴时受到防晒保护的奶牛的最大数量。
示例输入
3 2
3 10
2 5
1 5
6 2
4 1
示例输出
2
题目链接
https://vjudge.net/problem/POJ-3614
将奶牛按照SPF值的最小值从小到大排序。
将防晒霜也按照SPF的值从小到大排序
从最小的防晒霜枚举,将所有符合 最小值小于等于该防晒霜的奶牛的最大值 放入优先队列之中。
然后优先队列是小值先出
priority_queue<int, vector<int>, greater<int> > qi2;//从小到大的优先级队列,可将greater改为less,即为从大到小
AC代码
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 100000+5
using namespace std;
int C,L;
typedef pair<int,int> P;
priority_queue<int,vector<int>,greater<int> >q;//优先队列
P cow[Maxn],sun[Maxn];//奶牛 防晒霜
int main()
{
cin>>C>>L;
for(int i=;i<C;i++)//存数据
cin>>cow[i].first>>cow[i].second;
for(int i=;i<L;i++)
cin>>sun[i].first>>sun[i].second;
sort(cow,cow+C);//排序
sort(sun,sun+L);
int j=,ans=;
for(int i=;i<L;i++)
{
while(j<C&&cow[j].first<=sun[i].first)//奶牛FPS最小值小于防晒霜的FPS
{
q.push(cow[j].second);//奶牛入队
j++;
}
while(!q.empty()&&sun[i].second)
{
int now=q.top();
q.pop();
if(now<sun[i].first)//奶牛FPS最大值小于防晒霜的FPS,不符合
continue;
ans++;//若符合,则奶牛数+1
sun[i].second--;//防晒霜数量-1
}
}
cout<<ans<<endl;
return ;
}
最新文章
- 套题 codeforces 361
- 页面动态加入<;script>;标签并执行代码
- Spark SQL 官方文档-中文翻译
- OPENGL之矩阵
- 参数嗅探(Parameter Sniffing)(2/2)
- SHAREPOINT 工作流审批权限问题
- 【练习】数据文件的更改:改名或改路径 users01.dbf-->;users01_bak.dbf
- Android笔记(二):从savedIndstanceState发散
- 旧版asp.net 发送邮件代码
- iOS开发:详解Objective-C runTime
- apache安装扩展模块
- excel列显示形式互换(字母与数字)
- HTML5 拖拽效果实现
- linux查看硬盘占用情况
- 20175315 实验二《Java面向对象程序设计》实验报告
- Confluence 6 配置 XSRF 保护
- Windows 独立启动方式安装 Archiva
- python之random模块分析(一)
- LeetCode - Subtree of Another Tree
- UOJ #356. 【JOI2017春季合宿】Port Facility