| 题目名称 | 1585. [USACO Dec05]清理牛棚 |
|---|---|
| 输入输出 | clean.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 10 |
| 题目来源 |
 cstdio
于2014-04-12加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：36， 提交：90， 通过率：40% | ||||
 LGLJ |
100 | 0.000 s | 0.00 MiB | C++ |
 ┭┮﹏┭┮ |
100 | 0.000 s | 0.00 MiB | C++ |
|
liuyiche |
100 | 0.010 s | 5.73 MiB | C++ |
 Owaski |
100 | 0.021 s | 0.51 MiB | C++ |
 digital-T |
100 | 0.025 s | 0.46 MiB | C++ |
 mikumikumi |
100 | 0.028 s | 0.58 MiB | C++ |
 Qw |
100 | 0.030 s | 0.46 MiB | C++ |
|
liuyiche |
100 | 0.042 s | 7.58 MiB | C++ |
|
liuyiche |
100 | 0.046 s | 7.58 MiB | C++ |
|
梦那边的美好ET |
100 | 0.055 s | 7.35 MiB | C++ |
| 本题关联比赛 | |||
| 不准粘代码，必须自己写(HS除外) | |||
| 不准粘代码，必须自己写(HS除外) | |||
| 关于 清理牛棚 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
注意边界
| ||||
|
memset函数谁用谁是铁憨憨
| ||||
|
这是一道好题，可以写二分，最短路，线段树，甚至网络流
 ShallowDream雨梨
2019-07-31 10:21
7楼
| ||||
|
为什么开O2就错了？？！！
LGLJ
2019-06-11 17:56
6楼
| ||||
|
三楼大佬想法666...数据似乎有点水。
| ||||
| ||||
|
其实这道题可以抽象成一个最短路问题
将每个时间点作为一个点，每一头奶牛是一个路径，边权为花费。连接向起始时间点和终点+1（由于题目奇葩的规定- -） 然后为了解决覆盖问题所以从终时间点+1往起始点指，权值为0。 然后随便乱搞就过了。 // ----  ----> xwayne.com | ||||
|
线段树是啥。。。
 GDFRWMY
2014-04-13 17:29
2楼
| ||||
|
1D1D动归优化
三种方法：1.线段树（树状数组）；2.单调栈二分；3.优先队列 | ||||
Fisher.
0
waynest
cstdio【题目描述】
约翰的奶牛们从小娇生惯养。她们无法容忍牛棚里的任何脏东西。约翰发现，如果要使这群有洁癖的奶牛满意，它不得不雇佣她们中的一些来清扫牛棚。
约翰的奶牛中有N(1<=N<=10000)头愿意通过清扫牛棚来挣一些零花钱。由于在某个时段中奶牛们会在牛棚里随时随地地乱扔垃圾，自然地，她们要求在这段时间里，无论什么时候至少要有一头奶牛正在打扫。需要打扫的时段从某一天的第M秒开始，到第E秒结束（0<=M<=E<=86399）.注意这里的秒是指时间段而不是时间点。也就是说，每天需要打扫的总时间是E-M+1秒。
约翰已经从每头牛哪里得到了她们愿意接受的工作计划：对于每一头牛，她每天都愿意在第T1..T2秒的时间段内工作（M<=T1<=T2<=E），所要求的报酬是S美元（0<=S<=500000）。与需打扫时段的描述一样，如果一头奶牛愿意工作的时段是每天的第10..20秒，那她总共工作的时间是11秒，而不是10秒。约翰一旦决定雇佣某一头奶牛，就必须付给她全额的工资，而不能只让她工作一段时间，然后再按这段时间在她愿意工作的总时间中所占的百分比来决定她的工资。
现在请你帮约翰决定该雇佣那些奶牛以保持牛棚的清洁，当然，在能让奶牛们满意的前提下，约翰希望使总花费尽量小。
【输入格式】
第1行：3个正整数N,M,E，用空格隔开。
第2到N+1行：第i+1行给出了编号为i的奶牛的工作计划，即3个用空格隔开的正整数T1,T2,S.
【输出格式】
输出一个整数，表示约翰需要为牛棚清理工作支付的最少费用。如果清理工作不可能完成，那么输出-1.
【样例输入】
3 0 4 0 2 3 3 4 2 0 0 1
【样例输出】
5
【提示】
约翰有3头牛。牛棚在第0秒到第4秒之间需要打扫。第1头牛想要在0，1，2秒内工作，为此她要求的报酬是3美元，其余的依此类推。
【来源】
Coaches,2004
USACO DEC05 Silver,clean
Translate by：庄乐