新学知识：

T1：快速排序

快速排序（时间复杂度是O（nlog（n），有时会退化成$O(n^2))$

取一个基准值，使基准值左边的数都小于基准值，基准值右边的数都大于基准值。

快速排序的代码：

void quick_sort(int l,int r){
    if(l==r){
        return;//在void函数里面，return 0；
可以写成return;
    }
    int  x=f[l+r>>1],i=l-1,j=r+1;
    while(i<j){
        do i++;while(f[i]<x);
        do j --;while(f[j]>x);
    }
    quick_sort(l,j),quick_sort(j+1,r);
}

T2：归并排序

归并排序，时间复杂度是O（nlog（n））

把一个数组平均分半，直到分成一个数字，再把两个数字分成一组，两个数字之间排序，排号后把两组排在一起，以此类推，排完为止。

归并排序的代码：

void merge_sort(int q[],int l,int r){
    if(l>=r){
        return;//在void函数里面，return 0；
可以写成return;
    }
    int mid=(l+r)/2;//向下取整
    merge_sort(q,l,mid);
    merge_sort(q,mid+1,r);
    int k=0,i=1,j=mid+1;
    while(i<=mid&&j<=r){
        if(q[i]<=q[j]){
            temp[k]=q[i];
            k++;
            i++;
        }else{
            temp[k]=q[j];
            k++;
            j++;
        }
    }
    while(i<=mid){
        temp[k++]=q[i++];
    }
    while(j<=r){
        temp[k++]=q[j++];
    }
    for(int i=1,j=0;i<=r;i++,j++){
        q[i]=temp[j];
    }
}

T3：二分法

二分法指把一个有序的数组对半分开，取一个中间值，和要求的数字进行比较，如果中间值大于要求的数，那么判断的范围就缩短到了中间值的左边，否则判断的范围就是中间值的右边，以此类推，直到找到这个数字为止。

二分法的好处：每一次判断，判断的范围就缩短到一半。

二分法的代码：

bool check1(int mid){//mid是中间值
    if(a[mid>=x){
        return true;
    }else{
        return false;
    }
}
int bs1(int l,int r){
    while(l<r){
        int mid=(l+r)>>1;//向下取整
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;
}
bool check2(int mid){
    if(a[mid]<=x){
        return true;
    }else{
        return false;
    }
}
int bs2(int l,int r){
    while(l<r){
        int mid=(l+r+1)>>1;//向上取整
        if(check(mid)){
            l=mid;
        }else{
            r=mid-1;
        }
    }
    return l;
}

T2二分查找

二分查找指把一个有序的数组对半分开，取一个中间值，和要求的数字进行比较，如果中间值大于要求的数，那么判断的范围就缩短到了中间值的左边，否则判断的范围就是中间值的右边，以此类推，直到找到这个数字为止。

二分查找代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long n,m,maxn,sum,a[N];
bool check(int mid){
	for(long long i=0;i<n;i++){
		if(a[i]>mid){
			sum+=a[i]-mid;
		}
	}
	return sum>=m;
}
int main(){
	cin>>n>>m;
	for(long long i=0;i<n;i++){
		cin>>a[i];
		if(a[i]>maxn){
			maxn=a[i];
		}
	}
	long long l=0,r=maxn;
	while(l<r){
		long long mid=l+r+1>>1;
		if(check(mid)){
			l=mid;
			sum=0;
		}else{
			r=mid-1;
			sum=0;
		}
	}
	cout<<l;
    return 0;
}

此处以伐木工为例

定义l等于最小值，r等于最大值，求最小值和最大值中间的值，缩小判断范围，sum累加求和，判断是否大于m后输出。