CF-53B普及+/提高
博客照片
⏱ 2.0s💾 256MB
📋 题目描述
某博客的照片上传功能为:对于一张原照片,系统会裁剪其中的一个矩形部分上传,这个矩形部分被称为 “ 上传矩形 ” 。上传矩形的高宽比的合法取值范围为 至 。另外,上传矩形至少要有一条边的长度等于 ( 为整数 )且各边长度都为正整数。现在给出原照片的高度 和宽度 ,请你求出一个最大面积合法上传矩形,并给出它的高和宽 。
📥 输入格式
仅有一行包含两个整数 和 ( ) ,分别表示原照片的高和宽。
📤 输出格式
仅有一行包含两个整数,分别表示上传矩形的高和宽,如果有多个答案,则输出高最大的那一个。
📝 样例 1
输入
2 1
输出
1 1
📝 样例 2
输入
2 2
输出
2 2
📝 样例 3
输入
5 5
输出
5 4
📚 来源
Problem:CF-53B
💡 题目讲解
1
理解题意
从 的原照片里裁剪一个矩形,满足三个条件:
① 高宽比在 之间 — 即 。不能太扁,也不能太窄。
② 至少一条边是 — 即 1, 2, 4, 8, 16, ... 中的某个数。只要高或宽中有一个就行。
③ 边长不超过原照片 — 高 ,宽 。
🎯 找面积最大的合法裁剪。面积相同选高最大的。
用样例 1()试试:
原照片 2×1。可能的 2^x 边长:1, 2。
| 尝试 | 以哪边 = 2^x | 另一边 | 检查 |
|---|---|---|---|
| 高=1,宽=1 | 高=1(=2⁰) | ✓ | ✓ |
| 高=2,宽=1 | 高=2(=2¹) | ,但 | ✗ |
| 高=1,宽=2 | 宽=2(=2¹) | ✗ |
只有 1×1 合法 → 答案 "1 1" ✅。
1 / 5