题解 | #小美的梯子#
小美的梯子
https://www.nowcoder.com/practice/bd5627c6d0c14951b8072830e26a041b
题目链接
题目描述
小美使用 | 字符和 = 字符来建造梯子。一个梯子的基本结构是 |=|。多个梯子可以排成一行，并通过复用 | 字符连接，例如 |=|=| 是两个梯子。
给定 个
| 字符和 个
= 字符，求最多可以建造出多少个梯子。
解题思路
这是一个简单的资源分配问题。关键在于找出建造 个梯子需要多少
| 和 = 字符。
资源消耗分析
我们来观察一下梯子数量与所需材料的关系：
- 1 个梯子:
|=|。需要 2 个|和 1 个=。 - 2 个梯子:
|=|=|。需要 3 个|和 2 个=。 - 3 个梯子:
|=|=|=|。需要 4 个|和 3 个=。
通过观察，我们可以归纳出规律：
- 要建造
个梯子，需要
个
|字符。 - 要建造
=字符。
建立约束条件
我们手头有 个
| 和 个
=。设我们最多能造 个梯子。那么必须满足以下两个条件：
|字符的数量必须足够：=字符的数量必须足够：
从第一个条件可以推导出：。
结合第二个条件
，为了同时满足两者，
必须小于或等于这两个上限中的较小值。
因此，最大可能的梯子数量 就是：
边界情况
这个公式也优雅地处理了边界情况。
- 如果
|的数量不足以搭建一个梯子（即），那么
，
的结果将小于 1。由于梯子数必须是整数，最多能造 0 个，这是正确的。
- 如果
=的数量为 0（即），
的结果是 0，同样是正确的。
为了确保最终结果不为负数（例如当 时），我们可以取结果与 0 的最大值。
代码
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
long long n, m;
cin >> n >> m;
if (n < 2) {
cout << 0 << endl;
} else {
cout << min(n - 1, m) << endl;
}
return 0;
}
import java.util.Scanner;
import java.lang.Math;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
long n = sc.nextLong();
long m = sc.nextLong();
if (n < 2) {
System.out.println(0);
} else {
System.out.println(Math.min(n - 1, m));
}
}
}
import sys
def solve():
n, m = map(int, sys.stdin.readline().split())
if n < 2:
print(0)
else:
print(min(n - 1, m))
solve()
算法及复杂度
- 算法：数学/逻辑推导
- 时间复杂度：
。该解法只涉及几次基本的算术和比较操作，与输入大小无关。
- 空间复杂度：
