试题 历届试题 分巧克力(二分)

问题描述

　　儿童节那天有K位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
　　小明一共有N块巧克力，其中第i块是Hi x Wi的方格组成的长方形。


　　为了公平起见，小明需要从这 N 块巧克力中切出K块巧克力分给小朋友们。切出的巧克力需要满足：


　　1. 形状是正方形，边长是整数
　　2. 大小相同


　　例如一块6x5的巧克力可以切出6块2x2的巧克力或者2块3x3的巧克力。


　　当然小朋友们都希望得到的巧克力尽可能大，你能帮小Hi计算出最大的边长是多少么？

输入格式

　　第一行包含两个整数N和K。(1 <= N, K <= 100000)
　　以下N行每行包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000)
　　输入保证每位小朋友至少能获得一块1x1的巧克力。

输出格式

　　输出切出的正方形巧克力最大可能的边长。

样例输入

2 10
6 5
5 6

样例输出

2

思路

我的想法是直接以最大的正方形边长贪心往回找，直到满足跳出就是正确答案，复杂度是o(n^2)，规模是10的10次方，自然是tle，过了大部分样例，75分代码。

#include<algorithm>
#include<iostream>
using namespace std;
int h[100005], w[100005];
int main()
{
    int n, k;cin >> n >> k;
    for (int i = 0;i < n;i++)cin >> h[i] >> w[i];
    int i;
    for (i = 100000;i >= 1;i--) {
        int cot=0;
        for (int j = 0;j < n;j++) {
            cot += (h[j] / i) * (w[j] / i);///实现的细节
        }
        if (cot >=k)break;
    }
    cout << i << endl;
    return 0;
}

正解

要ac本题就需要想办法降低时间复杂度，正解是用二分降低规模，再枚举判定当前边长符不符合条件(这步没想到，总纠结怎么从二分直接得到答案），时间复杂度为o(n*logn)。

#include<algorithm>
#include<iostream>
using namespace std;
int h[100005], w[100005];
int n,k;
bool judge(int tot)
{
    int ans = 0;
    for (int i = 0;i < n;i++) {
        ans += (h[i] / tot) * (w[i] / tot);
    }
    if (ans >= k)return true;
    else return false;
}
int main()
{
    cin >> n >> k;
    for (int i = 0;i < n;i++)cin >> h[i] >> w[i];
    int left = 1, right = 10000;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (judge(mid)) {///如果成功，再测试能不能更大的巧克力
            left = mid + 1;
        }
        else {
            right = mid - 1;//失败，将巧克力变小
        }
    }
    while (!judge(left)) {
        left--;
    }
    cout << left << endl;
    return 0;
}