【BZOJ】3410: [Usaco2009 Dec]Selfish Grazing 自私的食草者(贪心)
2024-09-29 16:31:35
http://www.lydsy.com/JudgeOnline/problem.php?id=3410
太神了。。。。
按末端点排序然后贪心取即可。
QAQ
#include <cstdio>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
#define rep(i, n) for(int i=0; i<(n); ++i)
#define for1(i,a,n) for(int i=(a);i<=(n);++i)
#define for2(i,a,n) for(int i=(a);i<(n);++i)
#define for3(i,a,n) for(int i=(a);i>=(n);--i)
#define for4(i,a,n) for(int i=(a);i>(n);--i)
#define CC(i,a) memset(i,a,sizeof(i))
#define read(a) a=getint()
#define print(a) printf("%d", a)
#define dbg(x) cout << #x << " = " << x << endl
#define printarr(a, n, m) rep(aaa, n) { rep(bbb, m) cout << a[aaa][bbb]; cout << endl; }
inline const int getint() { int r=0, k=1; char c=getchar(); for(; c<'0'||c>'9'; c=getchar()) if(c=='-') k=-1; for(; c>='0'&&c<='9'; c=getchar()) r=r*10+c-'0'; return k*r; }
inline const int max(const int &a, const int &b) { return a>b?a:b; }
inline const int min(const int &a, const int &b) { return a<b?a:b; }
struct dat { int x, y; }a[50005];
int n;
bool cmp(const dat &a, const dat &b) { return a.y<b.y; }
int main() {
read(n);
for1(i, 1, n) read(a[i].x), read(a[i].y);
sort(a+1, a+1+n, cmp);
int ans=0, ed=0;
for1(i, 1, n) {
if(a[i].x>=ed) {
++ans;
ed=a[i].y;
}
}
print(ans);
return 0;
}
Description
约翰有N(1≤N≤50000)头牛,约翰的草地可以认为是一条直线.每只牛只喜欢在某个特定的范围内吃草.第i头牛喜欢在区间(Si,Ei)吃草,1≤Si<Ei≤1,000,000,00.
奶牛们都很自私,他们不喜欢和其他奶牛共享自己喜欢吃草的领域,因此约翰要保证任意
两头牛都不会共享他们喜欢吃草昀领域.如果奶牛i和奶牛J想要同时吃草,那么要满足:Si>=Ej或者Ei≤Sj.约翰想知道在同一时刻,最多可以有多少头奶牛同时吃草?
Input
第1行:一个整数N.
第2到N+1行:第i+l行有两个整数Si,Ei.
Output
一个整数,最多可以有多少头牛同时吃草.
Sample Input
5
2 4
1 12
4 5
7 10
7 8
2 4
1 12
4 5
7 10
7 8
Sample Output
3
HINT
第1,3,4共3只奶牛可以同时吃草,第1,3,5也可以.
Source
最新文章
- git亲测命令
- eclipse自动补全的设置
- [转]CISP(注册信息安全专业人员)认证(12天)
- activiti自定义流程之Spring整合activiti-modeler5.16实例(三):流程模型列表展示
- C# DEBUG 调试信息打印及输出详解
- js面向对象--类式继承
- Activity之间通过intent 传递Map
- 高级UNIX环境编程10 信号
- 对";一维最大子数组和";问题的思考
- python操作数据库之批量导入
- HashMap源码详解(JDK7版本)
- 看JQ时代过来的前端,如何转换思路用Vue打造选项卡组件
- 蓝桥杯练习系统—基础练习 2n皇后问题
- SLAM+语音机器人DIY系列:(三)感知与大脑——6.做一个能走路和对话的机器人
- Jetpack 架构组件 Paging 分页加载 MD
- 面向对象编程其实很简单--python面向对象(初级篇)
- MSF《构建之法》阅读笔记5
- django-celery定时任务以及异步任务and服务器部署并且运行全部过程
- 严格控制GOTO语句
- Android Studio Tips
热门文章
- vc 获取函数名称真实地址
- hdu 3572 Task Schedule(最大流&;amp;&;amp;建图经典&;amp;&;amp;dinic)
- jQuery基本选择 元素
- php json_decode失败,返回null
- ip地址库选择
- java基础讲解13-----集合
- html调用摄像头的方法汇总
- Windows+Nginx+IIS做图片分布式存储详细步骤
- 点滴积累【C#】---Highcharts图形统计
- atitit。企业组织与软件工程的策略 战略 趋势 原则 attilax 大总结