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

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

图片说明

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

题解

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

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

活动奖励:

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

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

.牛币兑换中心

牛客博客开通方式

  1. 如何开通牛客博客:https://www.nowcoder.com/discuss/202952
  2. 如何使用博客搬家功能:进入博客--->设置--->底部博客搬家
  3. 如果你对牛客博客有任何意见或建议:牛客博客意见反馈专贴
全部评论
https://blog.nowcoder.net/n/9d4c8e291fa24ab8aa0e37e33aed2bd8
点赞 回复
分享
发布于 2020-05-11 14:14
英特尔
校招火热招聘中
官网直投
https://blog.nowcoder.net/n/6c5729ebfca74a07b9fa2bd2889a9a75 今天的题比较简单
点赞 回复
分享
发布于 2020-05-11 14:29
https://blog.nowcoder.net/n/91c86b08c13544ff8044c7847617d4d1
点赞 回复
分享
发布于 2020-05-11 14:35
https://blog.nowcoder.net/n/496799779cb3496bae7b1b79d5ad9505
点赞 回复
分享
发布于 2020-05-11 18:22
https://blog.nowcoder.net/n/d03102615eae477187e0860d48c04e1f
点赞 回复
分享
发布于 2020-05-11 23:36
https://blog.nowcoder.net/n/0a825b16ee20440eb1a49f74f7183207
点赞 回复
分享
发布于 2020-05-12 11:06
并查集解法 https://blog.nowcoder.net/n/01b05570962f4e5b855447428bdc2c12
点赞 回复
分享
发布于 2020-05-12 14:25
https://blog.nowcoder.net/n/2affa62f2ee04980b481a711ac22f35e
点赞 回复
分享
发布于 2020-05-12 17:09
我来啦😁https://blog.nowcoder.net/n/3ccf9d1b0c59463b8e97660256861a52
点赞 回复
分享
发布于 2020-05-13 00:54
https://blog.nowcoder.net/n/0dc4a9251418426986ffe0d30e052ca3
点赞 回复
分享
发布于 2020-05-13 15:38
https://blog.nowcoder.net/n/1fce991bdbf54e6faca38672695dcae7
点赞 回复
分享
发布于 2020-05-15 21:55
https://blog.nowcoder.net/n/e98bcd8acdc94a8b856b22b9965734dd
点赞 回复
分享
发布于 2020-05-16 13:47
https://blog.nowcoder.net/n/a9f0e7929a69451dbf389d265cfb5e33
点赞 回复
分享
发布于 2020-05-17 14:44
https://blog.nowcoder.net/n/74c36de3dd2a4b59a6655c455bd470a7 还是贪心简单啊
点赞 回复
分享
发布于 2020-05-17 15:03
https://blog.nowcoder.net/n/53b3597a5adc45ec83c46dad515bb42c
点赞 回复
分享
发布于 2020-05-18 10:30
https://blog.nowcoder.net/n/be4db10e43d044b48494fa174f77cb4e
点赞 回复
分享
发布于 2020-05-18 23:46
https://blog.nowcoder.net/n/1b8b2fb4774040e8ba008a51cd01c666  我又来了
点赞 回复
分享
发布于 2020-05-21 12:27

相关推荐

1 2 评论
分享
牛客网
牛客企业服务