网站建设所面临的问题,做网站一年的维护费用是多少,门户网站的发展趋势,织梦做响应式网站分巧克力
题目描述
儿童节那天有 KKK 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NNN 块巧克力#xff0c;其中第 iii 块是 HiWiH_i \times W_iHiWi 的方格组成的长方形。
为了公平起见#xff0c;小明需要从这 NNN 块巧克力中切出 KKK…分巧克力
题目描述
儿童节那天有 KKK 位小朋友到小明家做客。小明拿出了珍藏的巧克力招待小朋友们。
小明一共有 NNN 块巧克力其中第 iii 块是 Hi×WiH_i \times W_iHi×Wi 的方格组成的长方形。
为了公平起见小明需要从这 NNN 块巧克力中切出 KKK 块巧克力分给小朋友们。切出的巧克力需要满足 形状是正方形边长是整数。 大小相同。
例如一块 6×56 \times 56×5 的巧克力可以切出 666 块 2×22 \times 22×2 的巧克力或者 222 块 3×33 \times 33×3 的巧克力。
当然小朋友们都希望得到的巧克力尽可能大你能帮小 HiH_iHi 计算出最大的边长是多少么
输入格式
第一行包含两个整数 NNN 和 KKK。(1≤N,K≤105)(1 \le N,K \le 10^5)(1≤N,K≤105)。
以下 NNN 行每行包含两个整数 HiH_iHi 和 WiW_iWi。(1≤Hi,Wi≤105)(1 \le H_i,W_i \le 10^5)(1≤Hi,Wi≤105)。
输入保证每位小朋友至少能获得一块 1×11 \times 11×1 的巧克力。
输出格式
输出切出的正方形巧克力最大可能的边长。
样例
样例输入
2 10
6 5
5 6样例输出
2提示
蓝桥杯 2022 省赛 A 组 I 题。
思路
还是得想到单调性要是能想到单调性这题就会很简单。 单调性是巧克力选择分得越小越能完成分巧克力 数据范围的原因只能使用O(nlogn)O(nlogn)O(nlogn)的算法。
代码实现
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int[][] arr;static int n, k;public static void main(String[] args) {Scanner sc new Scanner(System.in);//在此输入您的代码...n sc.nextInt();k sc.nextInt();arr new int[n][2];for(int i 0; i n; i){arr[i][0] sc.nextInt();arr[i][1] sc.nextInt();}int l 1, r 100000;while(l r){int mid (l r) / 2;if(check(mid)) l mid 1;else r mid - 1;}System.out.println(r);sc.close();}private static boolean check(int num){int ans 0;for(int i 0; i n; i){ans (arr[i][0] / num) * (arr[i][1] / num);if(ans k) return true;}return false;}
}
