题目名称	1435. [USACO NOV]金发姑娘和N头牛
输入输出	`milktemp.in/out`
难度等级	★★☆
时间限制	1000 ms (1 s)
内存限制	256 MiB
测试数据	20
题目来源	cqw 于2013-11-15加入
开放分组	全部用户
提交状态
分类标签	USACO 基本排序差分
	分享题解

通过：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了。 Shirry 2017-10-30 10:24 10楼
循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制循环控制 (用一个错误算法骗了95) Tanya 2017-10-22 20:57 9楼
离散化+差分 200t留念 CSU_Turkey 2017-09-05 11:55 8楼
扫描线第一题，纪念…… 啊吧啦吧啦吧 2015-07-27 20:55 7楼
回复 @Cirno : 玛德，rand不给力，没有大数据，回头加组极限的 cstdio 2013-11-19 12:55 6楼
回复 @cstdio : 用不到离散化 O（n）遍历可过，虽然常数时间会比离散化多那么点。。 Cirno 2013-11-19 08:21 5楼
边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值边界值 Cirno 2013-11-19 08:18 4楼
回复 @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)枚举 cstdio 2013-11-17 12:54 1楼

1435. [USACO NOV]金发姑娘和N头牛

★★☆ 输入文件：milktemp.in 输出文件：milktemp.out 简单对比
时间限制：1 s 内存限制：256 MiB

【题目描述】

你可能已经听说了金发姑娘和3只熊的经典故事。

鲜为人知的是，金发姑娘最终经营了一个农场。在她的农场，她有一个谷仓含N头奶牛（1<=N <= 20000)。不幸的是，她的奶牛对温度相当敏感。

第i头奶牛必须在指定的温度范围内A(i)..B(i)才感觉舒适；（0<=A(i)<=B(i)<= 1,000,000,000）。如果金发姑娘在谷仓放置一个温控器；如果温度T<A(i)，牛会太冷，并将产生x单位牛奶。如果她把恒温器调到（A(i)<=T<=B(i)）这个范围内,那么牛会感到舒适，并将产生Y单位牛奶。如果她把恒温器调到温度T>B(i)，牛会感觉很热，并将产生的Z单位牛奶。正如预期的那样，Y的值总是大于X和Z。

给定的X，Y，和Z，以及每个牛的温度的最佳范围，如果金发姑娘设置谷仓的温控器最佳，请计算金发姑娘得到牛奶的最大数量，已知X，Y和Z都是整数，范围0..1000。温控器可以设置为任意整数的值。

【输入格式】

第1行：四个用空格隔开的整数：N X Y Z。

第2行..1 + N：行1+i包含两个用空格隔开的整数：A(i)和B(i)。

【输出格式】

1行：金发姑娘最多可以获得的牛奶，当她在谷仓的最佳温度设定。

【样例输入】

4 7 9 6 5 8 3 4 13 20 7 10

【样例输出】

【提示】

在农场里有4头奶牛，温度范围5..8，3..4，13..20，10..7。一个寒冷的奶牛生产7单位的牛奶，一个舒适的奶牛生产9个单位的牛奶，一个热牛生产6单位牛奶。

【数据规模】

50%的测试数据：n<=5

其余50%的测试数据：10000<n<=20000.

【来源】

USACO 2013 November Contest, Bronze

translate by cqw

data from cstdio