二兵的赌注
Description
游戏中, 二兵要进入了一家奇怪的赌场
赌场中有 n 个庄家, 每个庄家都可以猜大猜小, 猜一次一元钱
每一次开彩前, 你都可以到任意个庄家那里下赌注
如果开彩结果是大, 你就可以得到你之前猜大的庄家相应的 ai 元钱
如果开彩结果是小, 你就可以得到你之前猜小的庄家相应的 bi 元钱
你可以在同一个庄家那里既猜大又猜小,(这样是两块钱), 也可以什么都不猜 (这样不用钱)
问怎么样下注, 才能赢得最多的有保障的钱
有保障的钱指不管开彩结果是大是小, 你都能够赢得相应的钱
你能帮助他计算这个值吗?
Input
第一行一个数字 N 表示有 N 个庄家
接下来 N 行, 每行 2 个实数, 分别表示这个庄家的 ai 和 bi
Output
一个四位小数, 表示最多能赢的有保障的钱
- Sample Input
- 4
- 1.4 3.7
- 1.2 2
- 1.6 1.4
- 1.9 1.5
- Sample Output
- 0.5000
- HINT
样例中, 最好的策略是赌第一个庄家开小, 第三第四个庄家开大
测试点 N
- 1 N10
- 2
- 3 N1000
- 4
- 5
- 6
- 7 N100000
- 8
- 9
- 10
- 1.0 ai, bi 1000.0
- 1s/128M
好了, 拿到题先花一定的时间弄清题意
然后我们就会发现: 押大小和哪个庄家之间完全没有关系, 一个庄家的大和小完全是独立的继续分析, 显然押越大的越好
于是我们分别 sort 一下
然后我开始了分析: 首先读入时 -=1, 然后, 设大或小为 a[] 和 b[], 分别取前 i.j 个押
然后对于每对确定的 i,j, 易知 s=min(suma[i]-j,sumb[j]-i) 其中 sum 为前缀和
我们设 suma[i]-j = 左, sumb[j]-i = 右
然后定性分析:
当 j 固定时, i + 则左 + 右 -,i - 则左 - 右 +
当 i 固定时, j + 则左 - 右 +,j - 则左 + 右 -
再次分析可知对于一对 (i,j), 若 i+, 则可能存在的 ans>s 必须令 j+
于是有了以下思路: for(i:1...n) 对于每个 i 找到匹配的 j, 则 i++ 时 j 不用从头开始枚举, 只需继续 j++, 于是时间复杂度 O(n) 完成 (不记 sort)
以上是我在考场上的思路不管思考过程多么艰难以至于花费 1hour 才想出来, 但是结果就是, 和标准程序简直一模一样但是代码实现上就很 naive 了
同一个思路, 我代码实现起来写了都要 40 + 行, 再一看标程, 不到十行就解决了, 尴尬......
我的代码大概是这样
来源: http://www.bubuko.com/infodetail-2497106.html