FZU 2203 单纵大法好 (二分 && 贪心)
题意 : 老S最近喜欢上某个搜集战舰的游戏,这个游戏中很重要的一个内容是能编排自己的战舰,通过出击完成任务来获取资源或新的战舰。大家都说老S是一个“直男”,所以他喜欢把战舰排成一条直线。目前老S正准备完成某个新的任务--“困难级丹麦海峡”,可以将地图视为1*N的一列方格(下标为1,2,...,N),老S有K列战舰,每列战舰长度为A。老S可以将自己的战舰布局在地图中的任意位置,但是两列战舰之间至少要有一个空格子,并且显然战舰是不能重叠放置的。老S通过内部人员率先知道了敌军的炮弹将会打向那些位置,老S希望使自己的舰队尽量晚的被第一次击中。请输出老S的舰队最晚将被敌方炮弹第一次击中?如果老S的舰队可以不被敌方炮弹击中则输出-1。
分析 : 可以考虑在1~N这个区间内一个个炸弹地增加去尝试是否能够避免被击中, 直到出现无法避免被击中的情况, 那此时答案就是这个炸弹了, 若直到N也就是炸弹全投放都能避免被击中, 那就输出-1。但是这样的话时间是线性的, 如果单看炸弹的轰炸顺序, 从第一个炸弹开始, 随着炸弹数的增加, 区间内被轰击的点越多, 也就是轰炸到的船的可能性越大, 这是单调的, 所以可以考虑二分来挑选炸弹。其中判定能否被击中可以采用贪心策略, 炸弹击中的点将区间划分为几个, 此时只要考虑这几个区间能够容纳下几只船, 如果都能容纳, 说明在不能击中船只, 继续二分增大炸弹数, 当然了, 这里轰炸点是需要排序的。还有一点需要注意=>就是题目有两艘船需要有一列间隔, 所以在计算安全区间的时候需要考虑到, 这里设 两炸弹围出的区间长度为empty, 船长度为len, 能容纳的船只数x(未知数) 故有 len*x+(x-1) <= emtpy 得 x<=(empty+1)/(len+1) , 考虑x的实际意义需要向下取整, 所以 x = (empty+1)/(len+1)
瞎搞 : 听说这种贪心+二分是一类题型, 自己完全没有想到一个个炸弹地增加这样去思考, 完全就是在乱想, 还是弱啊........
#include<iostream> #include<stdio.h> #include<string.h> #include<string> #include<algorithm> using namespace std; ; int temp[maxn], bomb[maxn]; ; bool Check(int x) { ; i<=x; i++){ temp[i] = bomb[i]; } sort(temp+, temp++x);//排序轰炸点, 方便贪心求出安全区间 ; temp[] = ; temp[x+] = N+; ; i<=x+; i++){ cnt = cnt + (temp[i]-temp[i-]+-)/(len+);//相当于(empty+1)/(len+1) } if(cnt>=K) return true; else return false; } int main(void) { while(~scanf("%d %d %d", &N, &K, &len)){ int M; scanf("%d", &M); ; i<=M; i++){ scanf("%d", &bomb[i]); } if(Check(M)){//如果M个炸弹一起上都能避免被轰击 puts("-1"); continue; } , R = M, mid; while(L <= R){//二分炸弹数 mid = (R + L)>>; ; ; } printf(); } ; }
最新文章
- webApp开发
- Unity3D上可以发布到IOS使用的SQLite数据库
- 如何在ubuntu里面关掉后台的meteor
- eclipse打包apk
- 【密码】Oracle用户密码系列
- 浅谈Mysql的MyIsam存储类型
- HTML <;base>; 标签的 target 属性 —— <;base target=";_blank"; />;
- 听说每天都要写随笔,word哥~
- 【项目】git的部署使用
- 在Tomcat中配置连接池和数据源
- [IOT] 自制蓝牙工牌办公室定位系统 (二)—— 基于ESP32的蓝牙信号扫描系统
- InstallShield:卸载时文字叠加,文字乱码
- Java Web(九) JDBC及数据库连接池及DBCP,c3p0,dbutils的使用
- 6.python3爬虫之urllib库
- java的基本数据类型--四类八种
- 面积并+扫描线 覆盖的面积 HDU - 1255
- Linux基础入门--04
- AM335X can驱动移植
- hdu 1075 What Are You Talking About 字典树模板
- 杂谈之界面设计和UI测试 (一)