CF1408D Searchlights
2021/10/15 6:15:00
本文主要是介绍CF1408D Searchlights,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
CF1408D Searchlights
题意:
在以左下角 \((0 , 0)\) 为坐标原点的直角坐标系中 , 有 \(n\) 个强盗 \(m\) 个监控。每个监控能看到自己左下角的所有区域。而所有强盗可以且只能同时向右或向上移动一步,求为了让所有强盗摆脱监控,最少移动次数为多少。
解法:
实际上这道题的图最终会形成这样:
观察可知,从上往下 \(x\) 轴能延伸到的位置单调递增。而且在上下两个相邻监控之间的部分,能延伸到的部分相同。
我们开一个数组 \(f_i\) 表示所有海盗先向上走了 \(i\) 步之后,最少要向右走几步。
处理这个数组需要的复杂度为 \(O(nm)\) ,具体实现如下:
for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(a[i] > c[j]) continue; f[c[j] - a[i]] = max(f[c[j] - a[i]] , d[j] - b[i] + 1); } }
然后再根据 \(x\) 随 \(y\) 单调递减可以得到:
若 \(y\) 越大,那么需要向右平移的位置越少。
所以我们就得到了以下写法:
int ans = 1e9 , last = 0; for(int i=MAXN;i>=0;i--){ last = max(last , f[i]); ans = min(ans , i + last); }
时间复杂度:
令 N = 1e6。
总复杂度为 \(O(nm + N)\)
Code
这篇关于CF1408D Searchlights的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-04el-table 开启定时器下,表格的选中状态会消失是什么原因-icode9专业技术文章分享
- 2024-10-03如何安装和初始化飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03如何安装 App 并连接到飞牛 NAS?-icode9专业技术文章分享
- 2024-10-03如何安装飞牛 TV 并连接到影视服务器?-icode9专业技术文章分享
- 2024-10-03如何在PVE和ESXI上安装飞牛私有云 fnOS?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS安装系统异常情况处理-icode9专业技术文章分享
- 2024-10-03飞牛NAS如何创建存储空间?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS硬盘会自动休眠吗?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何安装飞牛影视和创建媒体库?-icode9专业技术文章分享
- 2024-10-03fnOS国产最强NAS如何为家人朋友开通影视账号?-icode9专业技术文章分享