洛谷 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个防御塔
  

• 代码实现
  

[code]#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;pair  a[MAX],b[MAX];vector  edge[MAX];//哪些防御塔能打到这个敌人 int match[MAXK];//二分图匹配 bool vis[MAXK];double dis(int i,int j){//欧几里得距离         return sqrt((a.first-b[j].first)*(a.first-b[j].first)+(a.second-b[j].second)*(a.second-b[j].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