二分

1. 为什么用l+(r-l)/2?
   

数的三次方根

#include <cmath>
#include <iostream>
using namespace std;
double n;
int main() {
    cin >> n;
    double l = -10010, r = 10000;
    while (r - l >= 1e-9) {
        double mid = l + (r - l) / 2;
        if (pow(mid, 3) >= n)
            r = mid;
        else
            l = mid;
    }
    printf("%.6lf", r);
}

排列硬币
在超出n后，r = mid - 1是答案的由来

class Solution {
public:
    int arrangeCoins(int n) {
        long long l = 0, r = n;
        while (l <= r) {
            long long mid = l + (r - l) / 2;
            long long sum = mid * (mid + 1) / 2;
            if (sum == n) return mid;
            if (sum < n) l = mid + 1;
            else r = mid - 1;
        }
        return r;
    }
};

烦恼的高考志愿

#include <iostream>
#include <algorithm>
#include <cmath> // 用于abs()函数
using namespace std;

const int N = 100010;
int school[N], stu[N];
int m, n;

int main() {
    cin >> m >> n;
    for (int i = 0; i < m; i++) cin >> school[i];
    for (int i = 0; i < n; i++) cin >> stu[i];
    
    // 对学校分数线进行排序
    sort(school, school + m);
    
    long long sum = 0; // 使用 long long 防止可能的溢出
    for (int i = 0; i < n; i++) {
        int score = stu[i];
        int l = 0, r = m - 1;
        // 使用二分查找找到最接近学生估分的学校分数线
        while (l < r) {
            int mid = l + (r - l) / 2;
            if (school[mid] >= score) r = mid;
            else l = mid + 1;
        }
        // 检查与学生估分最接近的学校分数线是在左边还是右边
        int closest = school[l];
        if (l > 0) {
            int left_diff = abs(score - school[l - 1]);
            int right_diff = abs(score - closest);
            if (left_diff < right_diff) closest = school[l - 1];
        }
        
        sum += abs(score - closest);
    }
    
    cout << sum << endl;
    return 0;
}

木材加工

#include <iostream>
using namespace std;

const int N = 1e5+10;
long long a[N], n,k,sum,MaxLi;

bool check(int x){
	int s = 0;
	for(int i = 0;i < n;i++) s += a[i] / x;
	return s >= k;
}

int main(){
	cin >> n >> k;
	for(int i = 0;i < n;i++) {
		cin >> a[i];
		MaxLi = max(MaxLi,a[i]);
		sum += a[i];
	}
	if(sum < k) {
		cout << 0;
		return 0;
	}
	
	int l = 1,r = MaxLi;
	while(l<r){
		int mid = (l + r + 1) >> 1;
		if(check(mid)) l = mid;
		else r = mid-1;
	}
	cout << l;
}