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

思路

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

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

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

CPP

#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代码

CPP

#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;//好习惯
}

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

文章操作

思路

AC代码

相关推荐

评论

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