为了~~炫耀~~展现自己解决了这个同样困扰我的疑惑,于是来~~挖坟~~回答一下。
简单来说,就是贪心错了~~废话~~
这道题的奥妙在于一档志愿可能有多位导师。
理解了奥妙就能理解贪心为什么错了,如果你还理解不了,那就举个例子吧:
对于选手 $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