Cf Edu 15 C Cellular Network 二分

http://codeforces.com/problemset/problem/702/C 二分搜索与每个城市最近的信号塔 取能满足所有城市的最小值 #include<stdio.h> #include<string> #include<cstring> #include<queue> #include<algorithm> #include<functional> #include<vector> #include<iomanip> #include<math.h> #include<iostream> #include<sstream> #include<set> #include<map> using namespace std; const int MAX=100005; int A[MAX]={0},B[MAX]={0}; int main() { cin.sync_with_stdio(false); int n,m; cin>>n>>m; for (int i=0;i<n;i++) cin>>A[i]; for (int i=0;i<m;i++) cin>>B[i]; int Ans=0; for (int i=0;i<n;i++) { int d=lower_bound(B,B+m,A[i])-B; int res; if (d==0) res=B[d]-A[i]; else if (d==m) res=A[i]-B[d-1]; else res=min(B[d]-A[i],A[i]-B[d-1]); Ans=max(Ans,res); } cout<<Ans<<endl; return 0; } 直接二分答案 #include <bits/stdc++.h> using namespace std; __int64 a[1111111]; __int64 b[1111111]; int main() { int n,m; while (~scanf("%d%d",&n,&m)) { for (int i = 0 ; i < n ; i++ ) { scanf("%I64d",&a[i]); } for (int i = 0 ; i < m ; i++ ) { scanf("%I64d",&b[i]); } __int64 l = 0,r = 2000000008; while(l < r) { __int64 mid = (l + r) / 2; int flag = 0; int x = 0; for (int i = 0 ; i < n ; i++ ) { if ( x >= m) { flag = 1; break; } if (fabs(b[x] -a[i]) <= mid) { continue; } else { x++; i--; } } if ( flag == 1) { l = mid + 1; } else { r = mid; } //printf("%I64d\n",r); } printf("%I64d\n",l); } }