关于此题贪心和二分的疑惑

P4382 [八省联考 2018] 劈配

为了~~炫耀~~展现自己解决了这个同样困扰我的疑惑,于是来~~挖坟~~回答一下。 简单来说,就是贪心错了~~废话~~ 这道题的奥妙在于一档志愿可能有多位导师。 理解了奥妙就能理解贪心为什么错了,如果你还理解不了,那就举个例子吧: 对于选手 $i$,贪心求出了他需要上升到排名 $j$,原理在于 $i$ 替换了 $j$ 选到了对应的导师。 但是可能出现:将 $i$ 上升到排名 $j+1$,此时 $j$ 可能选择同一档志愿的另一位导师,而 $i$ 的导师就被让出来了(满足“前 $j+1$ 名的录取结果最优”)。显然,此时 $i$ 只需要上升到 $j+1$ 即可。 ------------ $\text{Action speaks louder than talk.}$ ------------ $Salmple:$ ``` 1 5 3 2 1 1 1 1 0 1 1 0 1 1 1 ``` $Wrong:$ ``` 1 1 3 0 0 2 ``` $Right:$ ``` 1 1 3 0 0 1 ```
by 约瑟夫用脑玩 @ 2020-06-13 17:16:30


反手一个 @[Dirt、](/user/91889)
by 约瑟夫用脑玩 @ 2020-06-13 17:19:40


|