蓝桥题库_分巧克力，C++

Question

问题： 儿童节那天有K 位小朋友到小明家做客。
小明拿出了珍藏的巧克力招待小朋友们。
小明一共有𝑁块巧克力，其中第𝑖i 块是𝐻𝑖×𝑊𝑖的方格组成的长方形。
为了公平起见，小明需要从这𝑁 块巧克力中切出 K 块巧克力分给小朋友们。
切出的巧克力需要满足：形状是正方形，边长是整数;大小相同;
例如一块6×5的巧克力可以切出6块2×2 的巧克力或者2块3×3的巧克力。
当然小朋友们都希望得到的巧克力尽可能大，你能帮小明计算出最大的边长是多少么？

蓝桥题库第99题——分巧克力
该代码只通过3/4的测试案例
未通过的案例N、K值为100000,100，然后100000个巧克力的边长
想请教一下问题在哪

#include<iostream>
using namespace std;
int main() {
     int N,K,side=0,sum=0;
     cin >> N >>K ;
     int resolute=0;
     int** chocolate = new int* [N];
     for (int i = 0; i < N; i++) {
          chocolate[i] = new int[2];
             for (int j = 0; j < 2; j++) {
                    cin >> chocolate[i][j];
            }
     }
     for (int i = 1; i < 100000; i++) {
             for (int j = 0; j < N; j++) {           
                    sum += (chocolate[j][0] / i) * (chocolate[j][1]/i);     
                }       
             if (sum < K) {
                 resolute = (i == 1) ? i : i - 1;
                 break;
             }
             else
                 sum = 0;
     }  
     for (int i = 0; i < N; i++) {
          delete[]chocolate[i];
     }delete[]chocolate;
     cout << resolute;
     return 0;
}

Answer 1

这个问题的代码逻辑上基本正确，但由于时间复杂度较高（特别是在 N 和 K 较大时），可能导致超时。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool canDistribute(int side, int K, const vector<pair<int, int>>& chocolates) {
    int count = 0;
    for (const auto& chocolate : chocolates) {
        count += (chocolate.first / side) * (chocolate.second / side);
        if (count >= K) return true;  // 提前返回，节省时间
    }
    return count >= K;
}

int main() {
    int N, K;
    cin >> N >> K;

    vector<pair<int, int>> chocolates(N);
    for (int i = 0; i < N; i++) {
        cin >> chocolates[i].first >> chocolates[i].second;
    }

    int left = 1, right = 1e5, max_side = 0; // 假设边长最大为100000

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (canDistribute(mid, K, chocolates)) {
            max_side = mid;  // 找到了一个可行解，尝试更大的边长
            left = mid + 1;
        } else {
            right = mid - 1;  // 尝试更小的边长
        }
    }

    cout << max_side << endl;
    return 0;
}