题意 给你一个环，有 个区间,区间之间互相不覆盖。求当任意一个区间必须选择时，最少需要多少个区间能够覆盖整个环。 思路 对于一个战士 ，如果选了他，那么下一个战士 一定是所有左端点小于等于 的右端点的战士中最大的一个战士，因为这样子才是是最优的。所以我们只需要预处理加二分找到下一个战士就好了
展开全文
[SCOI2015]国旗计划 注意一个关键点，没有一个区间是包含在另一个区间的，这意味着区间之间要么相交要么相离，当有一个区间一定加入时，我们可以二分查找去得到下一个区间的，但是这样速度显然太慢了，所以我们利用倍增来优化。 定义表示号节点为左端点，共有条线段连在一起最有可到达的坐标。然后只需要从小到
展开全文
非常考验技巧的一题...emm这个我最不会了... 首先断环为链,也就是把士兵和站台复制一份放在后面,这样只需要考虑覆盖一个区间而已 因为区间两两不包含,所以当选择了第个士兵后 现在覆盖了 那么从左端点不大于里选,一定是选右端点最大的最优秀了 那么这样选择的士兵就固定了... 关键就找下一个士兵的过
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
