[数据结构与算法]计蒜客 - T2063_导弹拦截

?

?

//
题解:

    将 导弹到两个系统的距离(d1 d2) 组成一个结构体 针对导弹到 1号系统的距离(d1) 从大到小进行排序
    然后进行遍历 当且仅当 a[i].d1 + ( 1~i-1 中 a[i].d2 的最大值 ) 最小时 就是答案
    注意 存在那么一种情况 1号系统不用拦截任何一枚导弹

    就相当于把导弹分成了两堆 求他们各自最大值之和就可 只不过先把其中一堆的最大值给排好了

//
#include<bits/stdc++.h>
using namespace std;

const int MAXN=1e5+6;

typedef struct missile
{
    int d1,d2;
}T;
T a[MAXN];

bool cmp( T a,T b )
{
    return a.d1>b.d1;   // 表达式的值
}

int main()
{
    int x1,yl,x2,y2,n,i,x,y,maxd2,ans;      // yl

    while( ~scanf("%d%d%d%d%d",&x1,&yl,&x2,&y2,&n) )
    {
        memset( a,0,sizeof( a ) );

        for( i=0;i<n;i++ )
        {
            scanf("%d%d",&x,&y);
            a[i].d1=( x1-x )*( x1-x )+( yl-y )*( yl-y );    // 负负得正
            a[i].d2=( x2-x )*( x2-x )+( y2-y )*( y2-y );
        }
        sort( a,a+n,cmp );

        ans=a[0].d1;                    // 初始化
        maxd2=a[0].d2;
        for( i=1;i<=n;i++ )             // i<=n: 1号系统可能无须拦截导弹
        {
            ans=min( ans,maxd2+a[i].d1 );
            maxd2=max( maxd2,a[i].d2 );
        }
        printf("%d\n",ans);
    }
    return 0;
}

//
find:
01 计算规模 1<=N<=1e5,abs<=1e3 --> d<=2*1e8 < int
02 cmp 直接 return 表达式的值
03 全局变量 y1 命名冲突 就用 yl yi 等等 ( 有一个头文件定义过了 y1 )
04 负负得正
05 初始化要到位(a[n]=0) 1号系统可能无须拦截导弹 
06 厘清逻辑关系

00 为什么一开始思路不对呢 

    有可能 前面 1号系统 的工作半径大 
    然后突然有一颗距离 2号系统 近一些的极远的导弹 
    导致直接把 1号系统 的工作半径给包括了

00 快读