关于容易想到的贪心但错了
查看原帖
关于容易想到的贪心但错了
699110
kelanjie楼主2023/3/27 19:59

一杯浓度大的糖水与另一杯糖水混合,另一杯糖水的浓度大不代表混合后的浓度大

如:7g糖,14g水为确定的一杯,称作 WW

然后还有两杯

AA 杯为7g糖,4g水, BB 杯为3g糖,0g水(浓度100100%,大不大)

然后 WWAA 混合后的浓度为 43.7543.75%

WWBB 混合后的浓度为41.66666.....41.66666.....%

下为闲话: 先想到二分浓度,然后想到 (假) 单调性,即前面提到的,然后枚举 nn 杯糖水,与剩下 mm 杯糖水混合是有(假的)单调性的,再进行二分看有多少混合后的糖水比当前 xx 浓度大,不断二分,调了好久,最后终于发现了这贪心假了(估计是因为我太菜了),下面放造的数据:

4 3 10
9 1
7 14
13 15
13 5
6 15
3 0
7 4

2023/3/27 19:59
加载中...