题目名称 | 1151. [长郡中学2004] 活动选择 |
---|---|
输入输出 | active.in/out |
难度等级 | ★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 128 MiB |
测试数据 | 10 |
题目来源 | Makazeu 于2012-10-16加入 |
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:172, 提交:387, 通过率:44.44% | ||||
Hakurou! | 100 | 0.000 s | 0.00 MiB | C++ |
面对疾风吧 疾风 疾风吧 | 100 | 0.000 s | 0.00 MiB | C++ |
面对疾风吧 疾风 疾风吧 | 100 | 0.000 s | 0.00 MiB | C++ |
cy | 100 | 0.000 s | 0.00 MiB | C++ |
joel | 100 | 0.000 s | 0.00 MiB | C++ |
xxcxcxcx | 100 | 0.000 s | 0.00 MiB | C++ |
wire | 100 | 0.000 s | 0.00 MiB | C++ |
能流零念 | 100 | 0.000 s | 0.00 MiB | C++ |
Harry Potter | 100 | 0.000 s | 0.00 MiB | C++ |
Harry Potter | 100 | 0.000 s | 0.00 MiB | C++ |
关于 活动选择 的近10条评论(全部评论) | ||||
---|---|---|---|---|
很强
白夜<=>黑天
2022-03-31 18:29
9楼
| ||||
可以,把按左端点排序换成右端点排序就A了尼玛。
| ||||
卧槽测试快读输入输出后忘了把printf("%d\n",n)删掉...
WA了这么多遍... | ||||
在循环中加上一个奇奇怪怪的判定就能快上不少
反正前几个0.003″的都是这样的 | ||||
看了楼上题解才发现方案最少数应该设成1...
Hakurou!
2016-07-04 14:50
5楼
| ||||
按起点排序贪心全W;按终点排序贪心全A。。
| ||||
裸的贪心么
| ||||
左端点排序动归,右端点排序贪心。
依然。。寒冰
2013-10-29 20:20
2楼
| ||||
搜索加各种初始化与基本剪枝A80
|
假设有一个需要使用某一资源的n个活动组成的集合S,S={1,2,……,n}。该资源一次只能被一个活动所占用,每一个活动有一个开始时间Bi和结束时间Ei(Bi<=Ei)。若Bi>Ej或者Bj>Ei,则称活动i和活动j兼容。
你的任务是:选择由互相兼容的活动组成的最大集合。
输入文件共有n+1行。
其中第一行包括一个整数n(2<=n<=1000),n表示活动的总数。
接下来的n行对应了这n个活动的开始时间和结束时间(中间用空格隔开)。
输出共1行,为最多的活动数。
11 3 5 1 4 12 14 8 12 0 6 8 11 6 10 5 7 3 8 5 9 2 13
4
被选中的活动可以是2、3、6、8号活动,总共有4项。