2021年寒假每日一題，2017~2019年的省賽真題，
本文內容由倪文迪（華東理工大學計算機系軟體192班）和羅勇軍老師提供，

后面的每日一題，每題發一個新博文，請大家看博客目錄：https://blog.csdn.net/weixin_43914593

2017省賽A類第9題，題目鏈接：
分巧克力 http://oj.ecustacm.cn/problem.php?id=1323

1、題目描述

有N個長方形，第i個長方形的邊長是Hi, Wi
把長方形分成相同的正方形，不少于K個，
問正方形最大的邊長是多少？
資料規模：1 <= N, K <= 100000，1 <= Hi, Wi <= 100000

2、題解

2.1 暴力

??先試試暴力，暴力的思路很簡單：把邊長從1開始到最大邊長D，每個值都試一遍，一直試到剛好夠分的最大邊長為止，
??編碼：邊長初始值d=1，然后d=2,3,4,…一個個試，
??暴力法的復雜度：n個長方形，長方形的最大邊長D，復雜度是 O ( n × D ) O(n \times D) O(n×D)，而n和D的最大值是10萬，會超時，
??暴力代碼：

#include<bits/stdc++.h>
using namespace std;
int h[100010],w[100010];
int n,k;
bool check(int d){ //檢查夠不夠分
    int num=0;
    for(int i=0;i<n;i++)
        num += (h[i]/d)*(w[i]/d);
    if(num>=k) return true;    //夠分
    else       return false;   //不夠分
}

int main(){
    cin >>n>>k;
    for(int i=0;i<n;i++)  cin>>h[i]>>w[i];
    int d=1;         //正方形邊長
    while(1){
        if(check(d))
           d++;    //邊長從1開始，一個個地暴力試試
        else
           break;
    }
    cout << d-1;
    return 0;
}

2.2 二分法

??既然一個個試邊長d太慢了，那就祭出二分大法，對邊長d的取值范圍二分，復雜度一下子從O(D)優化到了O(logD)，
??所謂二分法，就是每一次把搜索范圍減少一半，
??第一次：開始時d的范圍是1~D，試試中間值D/2，如果這個值大了，就把范圍縮小為0~D/2（如果這個值小了，就把范圍縮小為D/2~D）；
??第二次，取新的中間值D/4，再試…
??直到找到合適的值為止，
??二分法是一個基本的優化方法，二分法的學習，參考博文：
??https://blog.csdn.net/weixin_43914593/article/details/103250854
??這篇文章詳細介紹了二分法的原理、代碼、典型應用，

3、C++代碼

??整數的二分法的編碼雖然簡單，但是很容易出錯，左右邊界L、R和中間值mid的迭代，由于整數的取整問題，極易出錯，
??下面的整數二分代碼，給出了兩種寫法，請仔細體會，
??OJ運行時間77ms，

#include<bits/stdc++.h>
using namespace std;
int n,k;
int h[100010],w[100010];
bool check(int d){
    int num=0;
    for(int i=0;i<n;i++)
        num += (h[i]/d)*(w[i]/d);
    if(num>=k) return true;    //夠分
    else       return false;   //不夠分
}
int main(){
    cin >>n>>k;
    for(int i=0;i<n;i++)   cin>>h[i]>>w[i];

    int L=1, R=100010;
//整數二分法的L、R、mid如果處理不當，極容易死回圈，
//請仔細領會下面兩種寫法

//  第一種寫法：
    while(L<R) {
        int mid=(L+R+1)>>1;   //除2，向右取整
        if(check(mid))     
        	L=mid;  //新的搜索區間是右半部分，所以R不變，調整L=mid；
        else               
        	R=mid-1; //新的搜索區間是左半部分，所以L不變，調整R=mid–1，
    }
    cout << L;

//  第二種寫法：
/*  while(L<R) {
        int mid=(L+R)>>1;  //除2，向左取整
        if(check(mid))    
        	L=mid+1;//新的搜索區間是右半部分，R不變，更新L=mid+1，
        else
            R=mid;  //新的搜索區間是左半部分，L不變，更新R=mid
    }
    cout << L-1;
*/
    return 0;
}

4、Java代碼

??OJ上運行時間2.5s，

//newoj User:20185012;
import java.util.Scanner;
 
public class Main {
    private static int maxn = 100000;
    public static void main(String[] args) {
        int n,k;
        int[] h = new int[maxn];
        int[] w = new int[maxn];
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        k = scanner.nextInt();
        for (int i = 0; i < n; i++) {
            h[i] = scanner.nextInt();
            w[i] = scanner.nextInt();
        }
        int ans = 0;
        int right = maxn + 1;
        int left = 1;
        while (left<=right){
            int mid = (left + right) >> 1;
            int cnt = 0;
            for (int i = 0; i < n; i++) {
                cnt += (h[i] / mid) * (w[i] / mid);
            }
            if (cnt >= k){
                left = mid + 1;
                ans = mid; // 及時記錄結果!!!!!!
            }else
                right = mid - 1;
        }
        System.out.println(ans);
    }
}

5、Python代碼

??OJ運行時間1.5s，

def check(d):
    global w,h
    res = 0
    for i in range(len(w)):
        res += (w[i]//d) * (h[i]//d)
    if res >= k:  return True
    return False

n,k = map(int,input().split())
w = []
h = []
for i in range(n):
    a,b = map(int,input().split())
    w.append(a)
    h.append(b)

L ,R = 1, 10000
while L < R:
    mid = (L+R)//2
    if check(mid):  L = mid +1
    else :          R = mid
print(L-1)