1227. 分巧克力

WA 代码

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010;
int a[N];

int main(){
    int n, k;
    scanf("%d %d", &n, &k);
    int h, w;
    for(int i = 0; i < n; i ++ ){
        scanf("%d %d", &h, &w);
        int p = min(h, w), q = max(h, w);
        for(int j = p; j >= 1; j -- ){
            a[j] += (p / j) * (q / j);
        }
    }
    int res = 1;
    for(int t = 100000; t >= 1; t -- ){
        if(a[t] >= k){
            res = t;
            break;
        }
    }
    printf("%d", res);

    return 0;
}

AC 代码

在WA代码基础上优化：

#include <iostream>
#include <algorithm>
#define h first
#define w second

using namespace std;

const int N = 100010;
int n, k;
pair<int, int> choco[N]; // 存储每块巧克力的尺寸

bool check(int x) {
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += (choco[i].h / x) * (choco[i].w / x);
        if (cnt >= k) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &k);
    int maxSide = 0;
    for (int i = 0; i < n; ++i) {
        scanf("%d%d", &choco[i].h, &choco[i].w);
        maxSide = max(maxSide, min(choco[i].h, choco[i].w)); // 更新最大可能的边长
    }

    int l = 1, r = maxSide, res = 0;
    while (l <= r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            res = mid; // 如果当前 mid 可以，尝试更大的 mid
            l = mid + 1;
        } 
        else {
            r = mid - 1; // 如果当前 mid 不可以，降低 mid
        }
    }

    printf("%d\n", res);
    return 0;
}

另一种写法：

#include <iostream>
using namespace std;

const int N = 100010;
int n, k;
int h[N], w[N];

bool check(int x) {
    long long cnt = 0;
    for (int i = 0; i < n; ++i) {
        cnt += (h[i] / x) * (w[i] / x);
        if (cnt >= k) return true;
    }
    return false;
}

int main() {
    scanf("%d%d", &n, &k);
    for (int i = 0; i < n; ++i) scanf("%d%d", &h[i], &w[i]);

    int l = 1, r = 1e5; // 预设的边长搜索范围
    while (l < r) {
        int mid = l + (r - l + 1) / 2; // 向上取整避免死循环
        if (check(mid)) l = mid; // 如果可以切出足够的巧克力，尝试更大的边长
        else r = mid - 1; // 否则尝试更小的边长
    }
    printf("%d\n", l); // l 和 r 会收敛到最大的满足条件的边长
    return 0;
}