[Usaco2006 Open]County Fair Events 参加节日庆祝
Description
Farmer John has returned to the County Fair so he can attend the special events (concerts, rodeos, cooking shows, etc.). He wants to attend as many of the N (1 <= N <= 10,000) special events as he possibly can. He's rented a bicycle so he can speed from one event to the next in absolutely no time at all (0 time units to go from one event to the next!). Given a list of the events that FJ might wish to attend, with their start times (1 <= T <= 100,000) and their durations (1 <= L <= 100,000), determine the maximum number of events that FJ can attend. FJ never leaves an event early.
有N个节日每个节日有个开始时间,及持续时间. 牛想尽可能多的参加节日,问最多可以参加多少. 注意牛的转移速度是极快的,不花时间.
Input
Line 1: A single integer, N.
Lines 2..N+1: Each line contains two space-separated integers, T and L, that describe an event that FJ might attend.
Output
- Line 1: A single integer that is the maximum number of events FJ can attend.
Sample Input
7
1 6
8 6
14 5
19 2
1 8
18 3
10 6
Sample Output
4
首先按结束时间排序,然后一路搜下去,发现一个节日的开始时间在所记录的结束时间之后,就参加这个节日,同时更新记录的结束时间(典型贪心思想)
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define inf 0x7f7f7f
typedef long long ll;
typedef unsigned int ui;
typedef unsigned long long ull;
using namespace std;
inline int read(){
int x=0,f=1;char ch=getchar();
for (;ch<'0'||ch>'9';ch=getchar()) if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
return x*f;
}
inline void print(int x){
if (x>=10) print(x/10);
putchar(x%10+'0');
}
const int N=1e4;
struct AC{
int l,r;
void join(int x,int y){l=x,r=y;}
bool operator <(const AC &x)const{return r<x.r;}
}A[N+10];
int main(){
int n=read();
for (int i=1,x,y;i<=n;i++) x=read(),y=read(),A[i].join(x,x+y);
sort(A+1,A+1+n);
int x=A[1].r,ans=1;
for (int i=2;i<=n;i++) if (A[i].l>=x) x=A[i].r,ans++;
printf("%d\n",ans);
return 0;
}
最新文章
- UVA 624CD(01背包输出 + 输出路径)
- 单例模式-用GCD实现
- 轻量级iOS蓝牙库:LGBluetooth(项目中用过的)
- Sapi 添加语法的文章(转载)
- vbs xml 解析
- Python字符编码详解
- 解决 arcGis android TextSymbol乱码的问题
- Linux中与DNS相关的内容
- CreateFile使用方法和样例
- 第13天 JSTL标签、MVC设计模式、BeanUtils工具类
- Modis 陆地产品格网
- (四)Hololens Unity 开发之 凝视系统
- java数据结构(二叉树)
- ThreadLocal类分析
- NodeJS中的事件
- mysql数据库内容相关操作
- 私有云的难处—为什么需要CloudEngine?
- 关于 html input标签的几个常用操作
- 3ds max学习笔记(五)--操作工具
- 安装Intellij IDEA(ideaIU-2017.2.3)并完成Intellij IDEA的简单配置