P2255 [USACO14JAN]记录奥林比克Recording the M…
P2255 [USACO14JAN]记录奥林比克Recording the M…
题目描述
Being a fan of all cold-weather sports (especially those involving cows),
Farmer John wants to record as much of the upcoming winter Moolympics as
possible.
The television schedule for the Moolympics consists of N different programs
(1 <= N <= 150), each with a designated starting time and ending time. FJ
has a dual-tuner recorder that can record two programs simultaneously.
Please help him determine the maximum number of programs he can record in
total. 冬奥会的电视时刻表包含N (1 <= N <= 150)个节目,每个节目都有开始和结束时间。农民约翰有两台录像机,请计算他最多可以录制多少个节目。
输入输出格式
输入格式:
Line 1: The integer N.
- Lines 2..1+N: Each line contains the start and end time of a single
program (integers in the range 0..1,000,000,000).
输出格式:
- Line 1: The maximum number of programs FJ can record.
输入输出样例
6
0 3
6 7
3 10
1 5
2 8
1 9
4
说明
INPUT DETAILS:
The Moolympics broadcast consists of 6 programs. The first runs from time
0 to time 3, and so on.
OUTPUT DETAILS:
FJ can record at most 4 programs. For example, he can record programs 1
and 3 back-to-back on the first tuner, and programs 2 and 4 on the second
tuner.
Source: USACO 2014 January Contest, Silver
分析
如果只有一台的话直接贪心即可,两台呢,贪心也可以,多加一个变量,记录另一台摄像机到什么时间了即可
额能会有几种情况:
- 两台摄像机都在拍摄节目,这个节目也就拍不成了
- 有一台摄像机空闲,那就选这台拍
- 两台都空闲,那么找两者结束之前拍摄较晚的继续拍下去,另外一台留给后面的拍,这样选择余地更多(浪费也少)
注意结束时间还是可以用的,他在结束时间的前一分钟已经拍完了,手动测试样例发现的,难怪我调试不对orz。
代码
#include<cstdio>
#include<algorithm>
using namespace std; struct Que{
int l,r;
bool operator < (const Que &a) const
{
return r < a.r;
}
}q[]; int main()
{
int n,ans = , last1 = -,last2 = -;
scanf("%d",&n);
for (int i=; i<=n; ++i)
scanf("%d%d",&q[i].l,&q[i].r);
sort(q+,q+n+);
for (int i=; i<=n; ++i)
{
if (q[i].l<last1&&q[i].l<last2) continue ;
ans++;
if (q[i].l>=last1&&q[i].l<last2) last1 = q[i].r;
else if (q[i].l<last1&&q[i].r>=last2) last2 = q[i].r;
else if (last1<last2) last2 = q[i].r;
else last1 = q[i].r;
}
printf("%d",ans);
return ;
}
最新文章
- Windows bat脚本学习(1)
- viso
- LeetCode - Populating Next Right Pointers in Each Node
- 可复用View的PagerAdapter
- ConcurrentHashMap Put()操作示例代码
- 直接拿来用!最火的Android开源项目
- Hbase的Observer
- ajaxFileUpload增加附加参数
- sql 常用语法汇总
- EF的两种延迟加载
- svn问题(队列)
- Jedis实现发布订阅功能
- expdp之include参数——实现表级别的expdp操作
- SpringBoot全局日志管理(AOP)
- laravel项目安装
- linux telnet检测与某个端口是否开通
- JVM内存区域划分及垃圾回收
- AssetBundle自动标签、打包
- leftJoin鏈錶查詢
- a标签中可以加button,但是不提倡;button中不能加a标签,否则不能跳转