洛谷 P10936 导弹防御塔 题解
题目描述请移步 https://www.luogu.com.cn/problem/P10936[*]题目简述
有n个防御塔，每个防御塔都有充足的导弹
导弹需要一定时间发出，又需要一定时间冷却
导弹有确定的速度，发出后会沿最短路径攻击任意一个入侵者
有m个入侵者，给定防御塔和入侵者的坐标，求至少多久才能击退所有入侵者
[*]解题思路
经过分析，发现直接求最少多久似乎不太可行，于是考虑二分，将问题转化为验证一个时长是否可行
在一定时间内，每个防御塔可以发射固定数量个导弹，这些导弹必须可以击中所有的入侵者，否则不可行
我们可以处理出每个入侵者能被哪些导弹击中（第i个防御塔第1枚，第i个防御塔第2枚...），他必须被其中一枚击中
这有些类似二分图，将入侵者看作一类点，防御塔看作一类点，入侵者与能击中其的导弹连边
如果最大匹配小于入侵者数量，则不可行；反之，则可行
这样的复杂度或许有些高，但"N,M≤50"的数据还是可以通过的
[*]易错点
[*]题目中t1的单位是秒，需先转成分钟
[*]本题许多变量涉及小数，如t1，二分l_r_mid，还有check函数上传的量，注意使用double
[*]先输入的是m个入侵者的坐标，而非n个防御塔
[*]代码实现
#include #include #include #include #include #include using namespace std;const int MAX=55;const int MAXK=2505; const double eps=1e-7;//二分精度 int n,m;double t1,t2,v;paira,b;vectoredge;//哪些防御塔能打到这个敌人 int match;//二分图匹配 bool vis;double dis(int i,int j){//欧几里得距离 return sqrt((a.first-b.first)*(a.first-b.first)+(a.second-b.second)*(a.second-b.second));}bool find(int x){//二分图 for(int j=0;jt1>>t2>>v; t1=t1/60.0;//注意t1单位是秒 for(int i=1;i>b.first>>b.second;//入侵者 } for(int i=1;i>a.first>>a.second;//防御塔 } double l=0,r=1e9; while(r-l>eps){//小数二分 double mid=(l+r)/2.0; if(check(mid)==true){ r=mid; }else{ l=mid; } } cout 感谢分享，学习下。 谢谢楼主提供！ 感谢分享 很好很强大我过来先占个楼 待编辑
页:
[1]