M02774: 木材加工

binary search, http://cs101.openjudge.cn/practice/02774/

#include <stdio.h>

int len[10001];

bool check(int n, int m, int k){
	int cnt = 0;
	for (int i = 1; i <= n; i++){
		cnt += len[i] / m;
	}
	return cnt >= k;
}

int main(){
	int n, k, l = 1, r = 10000, ans = 0;
	scanf("%d %d", &n, &k);
	for (int i = 1; i <= n; i++){
		scanf("%d", &len[i]);
	}
	while (l <= r){
		int mid = (l + r) >> 1;
		if (check(n, mid, k)){
			l = mid + 1;
			ans = mid;
		} else {
			r = mid - 1;
		}
	}
	printf("%d", ans);
	return 0;
}

【黄宇曦 地球与空间科学学院】思路：直接二分解决，空间复杂度本来就是 $O(1)$。

#include <bits/stdc++.h>

using namespace std;

#define all(x) begin(x), end(x)
#define sz(x) (int) (x).size()

using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
using u128 = __uint128_t;
using pii = pair<int, int>;
using vi = vector<int>;
using usi = unordered_set<int>;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k;
    cin >> n >> k;
    vi a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (k > accumulate(all(a), 0ll)) {
        cout << 0 << '\n';
        return 0;
    }
    int l = 1, r = *max_element(all(a));
    auto check = [&](int x) {
        i64 ans = 0;
        for (int t : a)
            ans += t / x;
        return ans >= k;
    };
    int ans = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid))
            l = mid + 1, ans = mid;
        else
            r = mid - 1;
    }
    cout << ans << '\n';
    return 0;
}