题解 P1158 【导弹拦截】
安妮007
2017-10-07 19:50:23
这道题首先要明确所有导弹不是被1号系统拦截就是被2号系统拦截
我们看到这道题的数据范围是10的5次方,大概是nlogn复杂度,联想到sort排序
让我们思考一下最优解,在最优解中1号系统肯定先拦下距离自己近的
如果1号去拦距离它远的导弹的话,其实就捎带脚的把近的导弹拦截了
如果我们把所有导弹按照对1号的距离进行升序排序,通过刚才的思考我们知道肯定是1号拦截一个前缀,剩下的后缀交给2号
那么我们枚举一下这个前缀和后缀的分界点即可(分界点我们此处定义为前缀的最后一个点)
前缀处理的1号系统代价比较好算,就是分界点到1号系统的距离
2号系统此时就不能再排序看后缀谁是最大的来计算代价,此时需要我们预处理出来一个数组,让d[i]=包括第i以及它后面的导弹中最远距离
(思路来源于我的老师)
以下是AC题解
```cpp
#include<iostream>
#include<algorithm>//sort必须调用的库
using namespace std;
int x1,y1,x2,y2,n;//输入的五个数,为了cmp函数方便使用,开成全局变量
int d[100007];//预处理出来d数组,具体用途请看思路
struct node
{
int x;//记录导弹的位置信息
int y;
}w[100007];
bool cmp(node a,node b)
{
int q=(x1-a.x)*(x1-a.x)+(y1-a.y)*(y1-a.y);
int p=(x1-b.x)*(x1-b.x)+(y1-b.y)*(y1-b.y);
return(q<p);
}
int main(){
int ans=0;
cin>>x1>>y1>>x2>>y2;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>w[i].x>>w[i].y;
}
sort(w,w+n,cmp);
for(int i=n-1;i>=0;i--)
{
int h=(x2-w[i].x)*(x2-w[i].x)+(y2-w[i].y)*(y2-w[i].y);//预处理过程
d[i]=max(d[i+1],h);
}
ans=d[0];
for(int i=0;i<n;i++)
{
int cnt=0;
cnt=(x1-w[i].x)*(x1-w[i].x)+(y1-w[i].y)*(y1-w[i].y);
cnt+=d[i+1];//由于d[i]所保留的最大值包括i,而此时i属于前缀
ans=min(ans,cnt);
}
ans=min(ans,d[0]);
cout<<ans;
return 0;
}
```