18.[NOIP2010 普及组] 导弹拦截 难度：普及- 来源：-- AC代码（C++/C#）： * 没有注释，自行学习。 * by：ጿ ኈ ቼ ዽ ጿ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 你的点赞和关注就是我更新题解的最大动力！ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ——————————点个赞吧 ↓ ！——————————

#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; }

如果有两个导弹分别距离装置x1,x2（x1<x2） 显然此装备设置为x2便足以拦截此导弹 如果有n个也是如此 那么我们需要知道两个将装备拦截的导弹中距离最远的一个足以 那么就需要枚举 但是O(n^2)の枚举必定要T 那么我们需要线性枚举 但我们如果知道一个系统能拦截的导弹 那么剩下没拦截的导弹便有另一系统（ko na wo Dio da!!!）负责 那么我们可以线性枚举了

#include<bits/stdc++.h> using namespace std; struct Info{ int d1,d2; bool operator<(const Info &A){ return d1<A.d1; } }a[111111]; int n,X1,Y1,X2,Y2,f[111111]; int main(){ scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2); scanf("%d",&n); for(int i=1;i<=n;i++){ int x,y; scanf("%d%d",&x,&y); a[i].d1=(x-X1)(x-X1)+(y-Y1)(y-Y1); a[i].d2=(x-X2)(x-X2)+(y-Y2)(y-Y2); } sort(a+1,a+n+1); f[n+1]=0; for(int i=n;i;--i) f[i]=max(f[i+1],a[i].d2); int ans=1<<30; for(int i=0;i<=n;i++) ans=min(ans,a[i].d1+f[i+1]); printf("%d\n",ans); return 0; }

#include <iostream> #include <algorithm> // The library that sort must call using namespace std; int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function int d[100007]; // d array is preprocessed. See the idea for specific use struct node { int x; // Record the position information of the missile 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(void) { 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); // Pretreatment process 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]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix ans = min(ans,cnt); } ans = min(ans,d[0]); cout << ans; return 0; }

运行用时：42ms 内存消耗：3.02MB 虽然内存消耗有点大,不过运行还是蛮快的 另: 欢迎加入团队

#include <iostream> #include <algorithm> // The library that sort must call using namespace std; int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function int d[100007]; // d array is preprocessed. See the idea for specific use struct node { int x; // Record the position information of the missile 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(void) { 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); // Pretreatment process 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]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix ans = min(ans,cnt); } ans = min(ans,d[0]); cout << ans; return 0; }

#include <iostream> #include <algorithm> // The library that sort must call using namespace std; int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function int d[100007]; // d array is preprocessed. See the idea for specific use struct node { int x; // Record the position information of the missile 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(void) { 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); // Pretreatment process 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]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix ans = min(ans,cnt); } ans = min(ans,d[0]); cout << ans; return 0; }

#include <iostream> #include <algorithm> // The library that sort must call using namespace std; int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function int d[100007]; // d array is preprocessed. See the idea for specific use struct node { int x; // Record the position information of the missile 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(void) { 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); // Pretreatment process 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]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix ans = min(ans,cnt); } ans = min(ans,d[0]); cout << ans; return 0; }

#include <iostream> #include <algorithm> // The library that sort must call using namespace std; int x1,y1,x2,y2,n; // The five numbers entered are generated into global variables for the convenience of the cmp function int d[100007]; // d array is preprocessed. See the idea for specific use struct node { int x; // Record the position information of the missile 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(void) { 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); // Pretreatment process 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]; // Since the maximum value reserved by d [i] includes i, i belongs to the prefix ans = min(ans,cnt); } ans = min(ans,d[0]); cout << ans; return 0; }

#include<bits/stdc++.h> using namespace std; inline int dist(int x1,int y1,int x2,int y2){return (x1-x2)(x1-x2)+(y1-y2)(y1-y2);} struct Jack{ int l1,l2; }f[110000]; inline bool cmp(const Jack &a,const Jack &b){return a.l1<b.l1;} int main( ){ int n,i,j,k,x1,x2,y1,y2,a,b; stdiossync_with_stdio(false); cin>>x1>>y1>>x2>>y2; cin>>n; for(i=1;i<=n;i++){ cin>>a>>b; f[i].l1=dist(x1,y1,a,b); f[i].l2=dist(x2,y2,a,b); } sort(f+1,f+n+1,cmp); int ans=f[n].l1,hei=-1; for(i=n-1;i>=1;i--){ hei=max(hei,f[i+1].l2); ans=min(ans,hei+f[i].l1); } cout<<ans<<endl; }