| 题目名称 | 1435. [USACO NOV]金发姑娘和N头牛 |
|---|---|
| 输入输出 | milktemp.in/out |
| 难度等级 | ★★☆ |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试数据 | 20 |
| 题目来源 |
 cqw
于2013-11-15加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：64， 提交：147， 通过率：43.54% | ||||
 锝镆氪锂铽 |
100 | 0.001 s | 0.71 MiB | C++ |
 TA |
100 | 0.027 s | 0.72 MiB | C++ |
 Bennettz |
100 | 0.031 s | 0.44 MiB | C++ |
 hzx |
100 | 0.046 s | 0.47 MiB | C++ |
|
TA |
100 | 0.047 s | 0.46 MiB | C++ |
|
hzx |
100 | 0.047 s | 0.47 MiB | C++ |
|
TA |
100 | 0.050 s | 0.46 MiB | C++ |
|
Bennettz |
100 | 0.061 s | 0.38 MiB | C++ |
 NARUTO |
100 | 0.062 s | 0.42 MiB | C++ |
|
NARUTO |
100 | 0.063 s | 0.44 MiB | C++ |
| 关于 金发姑娘和N头牛 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
lower_bound和upper_bound~stl大法好。用查分维护一下就ok了。
| ||||
|
循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制
循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 (用一个错误算法骗了95)  Tanya
2017-10-22 20:57
9楼
| ||||
|
离散化+差分
200t留念 | ||||
|
扫描线第一题，纪念……
| ||||
|
回复 @Cirno :
玛德，rand不给力，没有大数据，回头加组极限的 | ||||
|
回复 @cstdio : 用不到离散化 O（n）遍历可过，虽然常数时间会比离散化多那么点。。
 Cirno
2013-11-19 08:21
5楼
| ||||
|
边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值
| ||||
|
回复 @Strawberry :
WTF我要改数据……  cstdio
2013-11-18 13:46
3楼
| ||||
|
梦迪说的我看不懂，不过我非常裸的枚举过了。。。
 Strawberry
2013-11-17 17:06
2楼
| ||||
|
排序。O(n)得到每个离散化后温度（因为最优温度一定是某个A[i]或某个B[i]）能产生多少个X和多少个Z，O(n)枚举
| ||||
Shirry
CSU_Turkey
啊吧啦吧啦吧【题目描述】
你可能已经听说了金发姑娘和3只熊的经典故事。
鲜为人知的是，金发姑娘最终经营了一个农场。在她的农场，她有一个谷仓含$N(1\leq N\leq 20000)$头奶牛。不幸的是，她的奶牛对温度相当敏感。
第$i$头奶牛必须在指定的温度范围内$A(i)\cdots,B(i)(0\leq A(i)\leq B(i)\leq 10^9)$才感觉舒适。
如果金发姑娘在谷仓放置一个温控器；如果温度$T<A(i)$，牛会太冷，并将产生$X$单位牛奶；如果她把恒温器调到$A(i)\leq T\leq B(i)$这个范围内,那么牛会感到舒适，并将产生$Y$单位牛奶；如果她把恒温器调到温度$T>B(i)$，牛会感觉很热，并将产生的$Z$单位牛奶。正如预期的那样，$Y$的值总是大于$X$和$Z$。
给定的$X$，$Y$和$Z(0\leq X,Y,Z\leq 1000)$，以及每个牛的温度的最佳范围，如果金发姑娘设置谷仓的温控器最佳，请计算金发姑娘得到牛奶的最大数量。温控器可以设置为任意整数的值。
【输入格式】
第一行为四个用空格隔开的整数：$N,X,Y,Z$。
接下来$N$行，每行两个用空格隔开的整数$A(i)$和$B(i)$。
【输出格式】
金发姑娘最多可以获得的牛奶，当她在谷仓的最佳温度设定。
【样例输入】
4 7 9 6 5 8 3 4 13 20 7 10
【样例输出】
31
【数据规模】
对于$50\%$的数据，$n\leq 5$；
对于$100\%$的数据，$n\leq 20000$。
【来源】
USACO 2013 November Contest, Bronze
translate by cqw
data from cstdio