【每日一题】5月12日题目精讲 贪心+搜索/并查集

题号 NC14698
名称 模拟战役
来源 中国矿业大学（北京）第二届ACM程序设计公开赛（决赛）
戳我进入往期每日一题汇总贴~
往期每日一题题单



如果你在题库做题时遇到了喜欢的题目，欢迎推荐给邓老师~ 点击查看详情

题解

首先我们要知道，如果a会引爆b那么b也会引爆a，也就是说我们可以把大炮分成若干个连通块，每个连通块内部只要一个被引爆找个连通块肯定就都炸了。这个用dfs/bfs/并查集都可以实现。
现在，我们求出来了齐齐和司机的每个连通块的大小和连通块个数，如果齐齐能摧毁司机的所有大炮那么他的联通块个数不能比司机的少。
那么在齐齐在能摧毁所有司机的情况下能最多剩下几门大炮呢？显然齐齐会有限选择损失少的大炮连通块去打（司机一炮回来这个连通块就没有自然应该选最小的连通块减少损失），所以对齐齐的连通块大小按从小到大排序然后依次使用直到把司机的大炮都消灭完即可。

看完邓老师的题解，记得自己去做题提高呀~
欢迎各位大佬来做题写题解，也欢迎大家踊跃在当日讨论贴中提问！

活动奖励：

在牛客博客中写出题解，并回复地址
审核通过可获得（依据题目难度和题解的内容而定）

本道题目5月19日中午12：00之前写的题解有获得牛币资格~

.牛币兑换中心

牛客博客开通方式

1. 如何开通牛客博客：https://www.nowcoder.com/discuss/202952
2. 如何使用博客搬家功能：进入博客--->设置--->底部博客搬家
3. 如果你对牛客博客有任何意见或建议：牛客博客意见反馈专贴