Codeforces 777E Hanoi Factory

Codeforces 777E Hanoi Factory

题目链接

http://codeforces.com/contest/777/problem/E

题目大意

有一个类似于汉诺塔的游戏,只是每个圆盘中间都是空心的,一个环 $i$ 能放在另一个环 $j$ 上当且仅当它的外半径小于 $j$ 环的外半径且外半径大于 $j$ 环的内半径,否则它将掉下去。现在已知每个环的高度,需要你求出最高能摆多高。

题目分析

这题注意到一个性质,如果对于一个环 $i$ ,它因为外半径过小无法放到圆环 $j$ 上,那么所有外半径小于等于 $i$ 的均无法放到圆环 $j$ 上。那么可以贪心求解。先将所有的圆环按外半径大小从大到小排序,如果外半径相同则按内半径大小从大到小排序,用栈来维护当前已经搭好的汉诺塔部分,每放进一个新的圆盘,将栈顶所有无法放它的圆盘全部弹出,记录高度,取最大值即可

时间复杂度: $O(N \times \log_{2}{N})$

代码

 

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注

Scroll Up