今天校赛D题 打气球那道题，复杂度必须小于O(N2)才能通过吗

听说是用一个二分答案的方法来优化，虽然我也是今天才听说这个方法的

你算算时间复杂度。。 正解是O(N*log(N)*log(H+NS)) 不过话说怎么N^2做啊。。你确定算法是对的？

跪求高效算法思路，我用笨法做的，从最后时刻向前，找每个时刻的最低的气球，然后打掉，所有最小值中的最大值就是答案，不过果断超时 【 在 samuelwyf (birdstorm) 的大作中提到: 】 : 你算算时间复杂度。。 : 正解是O(N*log(N)*log(H+NS)) : 不过话说怎么N^2做啊。。你确定算法是对的？ 通过『我邮2.0』发布

二分答案？？？高，实在是高。不过话说好多A掉该题的，有那么简单吗？ 【 在 ayzmkk (ayzmkk) 的大作中提到: 】 : 听说是用一个二分答案的方法来优化，虽然我也是今天才听说这个方法的 通过『我邮2.0』发布

你这个算法复杂度最坏是(H+NS)*N，都快10^12次方了。。你自己可以试试写个for循环看要跑多少时间。。 正解二分最终答案高度，这样我们可以知道每个气球到达这个高度的最晚时间 ，对这个时间排序后扫一遍，每秒贪心击落最早到达这个高度的气球，就可以判断这个高度是否合法。 【 在 tangyubin 的大作中提到: 】 : 跪求高效算法思路，我用笨法做的，从最后时刻向前，找每个时刻的最低的气球，然后打掉，所有最小值中的最大值就是答案，不过果断超时 : : 通过『我邮2.0』发布

二分答案果然巧妙，领教了[em68] 【 在 samuelwyf (birdstorm) 的大作中提到: 】 : 你这个算法复杂度最坏是(H+NS)*N，都快10^12次方了。。你自己可以试试写个for循环看要跑多少时间。。 : 正解二分最终答案高度，这样我们可以知道每个气球到达这个高度的最晚时间 ，对这个时间排序后扫一遍，每秒贪心击落最早到达这个高度的气球，就可以判断这个高度是否合法。 通过『我邮2.0』发布

进口学习 发自「贵邮」

我也果断超时[ema1][ema1] 【 在 ayzmkk (ayzmkk) 的大作中提到: 】 : 听说是用一个二分答案的方法来优化，虽然我也是今天才听说这个方法的

二分正解