二分答案

在单调符合答案的范围中找到极值

最小值最大化模板

//如果要求的内容在某个值以下的范围，要求这个范围的最大值
while(l<=r){
    int mid=l+r>>1;
    if(f(mid)) r = mid-1;
    else l = mid+1;
}
cout << r;

最大值最小化模板

//如果要求的内容在某个值以上的范围，要求这个范围的最小值
while(l<=r){
    int mid=l+r>>1;
    if(f(mid)) l = mid+1;
    else r = mid-1;
}
cout << l;

文件读写

freopen("D.in", "r", stdin);
freopen("D.out", "w", stdout);

第1题

#include <bits/stdc++.h>
using namespace std;

const int N=2e5+5;
int n, m;
int a[N];
int main() {
    freopen("D.in", "r", stdin);
    freopen("D.out", "w", stdout);
    cin >> n >> m;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);

    while(m--){
        int x;
        cin >> x;
        //通过二分法去找到n个数字当中与x差最小的数字，把差值加上
        int l=1, r=n;
        int flag = 0;
        while(l<=r){
            int mid = (l+r) / 2;
            if(a[mid] == x){
                cout << 0 << endl;
                flag = 1;
                break;
            }
            else if(a[mid] > x) r = mid-1;
            else l = mid+1;
        }
        if(flag==0){
            if(r<1) cout << a[1] - x << endl;
            else if(l>n) cout << x - a[n] << endl;
            else cout << min(x-a[r], a[l]-x) << endl;
        }
    }
    return 0;
}