二分两种的用法

佚名 6年前 (2019-04-17) 随笔 1356人围观抢沙发百度已收录

F - Cellular Network

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 7;

int a[maxn],b[maxn];


int main(){
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;
int sum  = 0;
for(int i = 0 ;i < n; i ++){
        //查找第一个大于或者等于a[i]的值
    //int x = lower_bound(b,b+m,a[i]) - b;
    //查找第一个大于的值的位置
    //查找与t相等的值的个数
    //abs(lower_bound(a+i+1,a+n,t) - upper_bound(a+i+1,a+n,t));
    int x = upper_bound(b,b+m,a[i]) - b;
    if(x == 0)
        ans = abs(a[i] - b[x]);
    else if(x == m)
        ans = abs(a[i] - b[x-1]);
    else
        ans = min(abs(a[i] - b[x-1]),abs(a[i] - b[x]));
    sum = max(ans , sum);

}
cout << sum << endl;
return 0;
}