题解：P1158 [NOIP 2010 普及组] 导弹拦截

Bearbrother18 · 2025-02-10 15:35:23 · 题解

思路

神犇们都用的贪心，但是我发现题目标签是（模拟，枚举，排列）。所以蒟蒻在这里发一篇用排列的题解。

我们可以用 pair 来储存每颗导弹到一号和二号系统的距离。不知道 pair 的点击这里。

然后对导弹的距离进行排序，我们按照一号到导弹的距离排序，这样当导弹超出一号系统的最远距离时，我们再用二号系统拦截。这时 pair 的优点就体现出来了，当我们用 sort 给 pair 排序时，它的第二组的顺序是按照第一组数据的顺序排列的。不理解的运行下面的代码就知道了。

#include <bits/stdc++.h>

using namespace std;

pair <int,int> a[10];

int main(){
    for(int i=1; i<=5; i++){
        cin >> a[i].first >> a[i].second;
    }
    sort(a+1,a+5+1);
    for(int i=1; i<=5; i++){
        cout << a[i].first << "    " << a[i].second << endl;
    }

    return 0;
}
/*
3 8
4 6
7 1
2 9
6 3
*/

每次拦截记录最新答案，最后输出即可。

AC代码

#include <bits/stdc++.h>

using namespace std;

int x1,yl,x2,y2,n,r,ans=1e8;
pair <int,int> a[100005];

int main (){
    cin >> x1 >> yl >> x2 >> y2;
    cin >> n;
    for(int i=1; i<=n; i++){
        int x,y;
        cin >> x >> y;
        a[i]={pow((x1-x),2)+pow((yl-y),2),pow((x-x2),2)+pow((y-y2),2)};
    }
    sort(a+1,a+n+1);//按一号顺序从小到大排列
    for (int i=n; i>=0; i--){
        ans=min(ans,a[i].first+r);
        r=max(r,a[i].second);
    }
    cout << ans;

    return 0;//好习惯
}