二分答案--木材加工-JZTXT

P2440 木材加工 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

直接暴力枚举如下：

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
long long arr[N];
int n, target;

bool check(int goal) {
    long long  ans = 0;
    for (int i = 0; i < n; i++)
        ans += arr[i] / goal;
    return ans >= target;
}

int main() {

    cin >> n;//个数
    cin >> target;//目标段数
    long long  maxx = -1;
    for (int  i = 0; i < n; i++) {
        cin >> arr[i];
        maxx = max(maxx, arr[i]);
    }
    int res = 0; //记录答案
    for (int i = 1; i <= maxx; i++) {
        if (check(i))
            res = i;
    }
    cout << res;



}

优化后全部AC：

//二分答案的做法---Ac
#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
long long arr[N];
int n, target;
bool check(int goal) {
    long long  ans = 0;
    for (int i = 0; i < n; i++)
        ans += arr[i] / goal;
    return ans >= target;
}
int main() {

    cin >> n;//个数
    cin >> target;//目标段数
    long long  maxx = -1;
    for (int  i = 0; i < n; i++) {
        cin >> arr[i];
        maxx = max(maxx, arr[i]);
    }
    int l = 0;
    int r = maxx;
    while (l + 1 < r) {
        int mid = (l + r) / 2;
        if (check(mid))
            l = mid;
        else
            r = mid;
    }
    cout << l << endl;
}