归并排序

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

int n;
int a[105];

//合
//left是左半边区域的左边界，mid是左半边区域的右边界，right是右半边的右边界
void hebing(int a[], int left, int mid, int right){
    //l1,r1分别表示左半边区域的左右边界
    //l2,r2分别表示右半边区域的左右边界
    int b[105] = {};  //b数组作为中间数组
    int idx = left;  //从b数组的第left个位置存放，因为a数组是从left-》right
    int l1=left, r1=mid, l2=mid+1, r2=right;
    while(l1<=r1 && l2<=r2){  //左半边区域 和 右半边区域都还有数字
        if(a[l1] <= a[l2]) b[idx] = a[l1], idx++, l1++; 
        else b[idx] = a[l2], idx++, l2++;
    }
    //假设左半边区域没有放完
    while(l1<=r1) b[idx] = a[l1], idx++, l1++;
    //假设右半边区域没有放完
    while(l2<=r2) b[idx] = a[l2], idx++, l2++;

    //按照顺序把中间数\组的数字放入a数组
    for(int i=left; i<=right; i++) a[i] = b[i];
}

//分
void fen(int a[], int left, int right){
    if(left<right){
        int mid = (left+right) / 2;
        fen(a, left, mid);  //分左半边
        fen(a, mid+1, right);   //分右半边
        hebing(a, left, mid, right);  //把左右合并
    }  
}
int main(){
    cin >> n;
    for(int i=1; i<=n; i++) cin >> a[i];  //乱序数组

    fen(a, 1, n); 
    for(int i=1; i<=n; i++) cout << a[i] << " "; 
    return 0;
}

二分答案

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

最小值最大化模板

//如果要求的内容在某个值以下的范围，要求这个范围的最大值
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=1e5+5;
int n,c;    //n表示n个牛棚，c表示有c头牛互相不服要干架
int a[N];   //a[i]表示第i个牛棚的位置

bool buheli(int mid){
    //xianfangdiyitouniu,baozhengzhishaoyouyitouniukeyifang
    int cnt = 1;  //先放第一头牛，保证至少有一头牛可以放
    int now = 1;  //设置最近的这头牛的位置
    for(int i=2; i<=n; i++){  //遍历2-n的位置，看能否放新牛
        //第i个位置和现在的牛的位置距离大于等于mid
        if(a[i] - a[now] >= mid){   
            cnt++;
            now = i;
        }
    }
    return cnt<c;
}

int main() {
    cin >> n >> c;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+1+n);

    //二分：两头牛之间的最短距离
    int l=1, r=a[n];
    while(l<=r){
        int mid = (l+r) / 2;  //假设两头牛之间的最短距离是mid
        if(buheli(mid)) r = mid-1;  //距离是mid的时候不合理
        else l = mid+1;   //距离是mid的时候合理
    }
    cout << r;
    return 0;
}