• 如果您觉得本站非常有看点,那么赶紧使用Ctrl+D 收藏吧

倪文迪陪你学蓝桥杯2021寒假每日一题:1.11日(2017省赛A第9题)

互联网 diligentman 5天前 7次浏览

2021年寒假每日一题,2017~2019年的省赛真题。
本文内容由倪文迪(华东理工大学计算机系软件192班)和罗勇军老师提供。

后面的每日一题,每题发一个新博文,请大家看博客目录https://blog.csdn.net/weixin_43914593

文章目录

  • 1、题目描述
  • 2、题解
    • 2.1 暴力
    • 2.2 二分法
  • 3、C++代码
  • 4、Java代码
  • 5、Python代码

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)


喜欢 (0)