蓝桥杯 prev37 分巧克力

蓝桥杯 prev37 分巧克力

问题描述

⼉童节那天有K位⼩朋友到小明家做客。⼩明拿出了珍藏的巧克⼒招待⼩朋友们。 ⼩明⼀共有N块巧克⼒,其中第i块是Hi x Wi的⽅格组成的⻓⽅形。 为了公平起⻅,⼩明需要从这 N 块巧克⼒中切出K块巧克⼒分给⼩朋友们。切出的巧克⼒需要满⾜:

  1. 形状是正⽅形,边⻓是整数
  2. ⼤⼩相同

例如⼀块6×5的巧克⼒可以切出6块2×2的巧克⼒或者2块3×3的巧克⼒。 当然⼩朋友们都希望得到的巧克⼒尽可能⼤,你能帮⼩Hi计算出最⼤的边⻓是多少么?

输⼊格式

第⼀⾏包含两个整数N和K。(1 <= N, K <= 100000) 以下N⾏每⾏包含两个整数Hi和Wi。(1 <= Hi, Wi <= 100000) 输⼊保证每位⼩朋友⾄少能获得⼀块1×1的巧克⼒。

输出格式

输出切出的正⽅形巧克⼒最⼤可能的边⻓。

样例输⼊

2 10 6 5 5 6

样例输出

2

数据规模和约定

峰值内存消耗(含虚拟机) < 256M CPU消耗 < 1000ms 请严格按要求输出,不要画蛇添⾜地打印类似:“请您输⼊…” 的多余内容。 注意: main函数需要返回0; 只使⽤ANSI C/ANSI C++ 标准; 不要调⽤依赖于编译环境或操作系统的特殊函数。 所有依赖的函数必须明确地在源⽂件中 #include <xxx> 不能通过⼯程设置⽽省略常⽤头⽂件。 提交程序时,注意选择所期望的语⾔类型和编译器类型。

解答

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <iostream>
#include <stdio.h>
#include <cmath>

using namespace std;

int n, k, l = 1, r = 0xffffff;
int h[100001], w[100001];

bool check(int a) {
int res = 0;
for (int j = 0; j < n; j++) {
res += (h[j] / a) * (w[j] / a);
if (res >= k)
return true;
}
return false;
}
int main() { // 二分查找
scanf("%d%d", &n, &k);
for(int i = 0; i < n; i++)
scanf("%d%d", &h[i], &w[i]);
while (l <= r) {
int mid = (l + r) / 2; // 此次边长
bool flag = check(mid);
if (flag && !check(mid+1)) { // 最大边长
cout << mid << endl;
break;
}
if (flag)
l = mid + 1;
else
r = mid - 1;
}
return 0;
}
/* 暴力搜索,从大到小
int main() {
int n, k, h[100001], w[100001];
double area = 0;
int r, res = 0;
scanf("%d%d", &n, &k);
for(int i =0; i < n; i++) {
scanf("%d%d", &h[i], &w[i]);
area += h[i] * w[i];
}
r = int(sqrt(area/k)); // 最大边长
for (; r >= 1; --r) {
for(int i = 0; i < n; ++i)
res += (h[i] / r) * (w[i] / r);
if (res >= k)
break;
}
cout << r << endl;
return 0;
}
*/

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×