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

最新文章

  1. 套题 codeforces 361
  2. 页面动态加入&lt;script&gt;标签并执行代码
  3. Spark SQL 官方文档-中文翻译
  4. OPENGL之矩阵
  5. 参数嗅探(Parameter Sniffing)(2/2)
  6. SHAREPOINT 工作流审批权限问题
  7. 【练习】数据文件的更改:改名或改路径 users01.dbf--&gt;users01_bak.dbf
  8. Android笔记(二):从savedIndstanceState发散
  9. 旧版asp.net 发送邮件代码
  10. iOS开发:详解Objective-C runTime
  11. apache安装扩展模块
  12. excel列显示形式互换(字母与数字)
  13. HTML5 拖拽效果实现
  14. linux查看硬盘占用情况
  15. 20175315 实验二《Java面向对象程序设计》实验报告
  16. Confluence 6 配置 XSRF 保护
  17. Windows 独立启动方式安装 Archiva
  18. python之random模块分析(一)
  19. LeetCode - Subtree of Another Tree
  20. UOJ #356. 【JOI2017春季合宿】Port Facility

热门文章

  1. django-session的使用---文件session型
  2. 模板方法(Template Method)---行为型
  3. 2018CCPC桂林站G Greatest Common Divisor
  4. 使用Hangfire处理后台任务
  5. Python图形用户界面-Tkinter
  6. Mybatis源码学习之类型转换(四)
  7. Oracle中将密码有效期由默认的180天修改成“无限制”
  8. div设置百分比高度 宽度
  9. SpringBoot整合guava缓存
  10. iSCSI存储技术