题目链接

小美的梯子

题目描述

小美使用 | 字符和 = 字符来建造梯子。一个梯子的基本结构是 |=|。多个梯子可以排成一行，并通过复用 | 字符连接，例如 |=|=| 是两个梯子。

给定 个 | 字符和 个 = 字符，求最多可以建造出多少个梯子。

解题思路

这是一个简单的资源分配问题。关键在于找出建造 个梯子需要多少 | 和 = 字符。

资源消耗分析

我们来观察一下梯子数量与所需材料的关系：

  • 1 个梯子: |=|。需要 2 个 | 和 1 个 =。
  • 2 个梯子: |=|=|。需要 3 个 | 和 2 个 =。
  • 3 个梯子: |=|=|=|。需要 4 个 | 和 3 个 =。

通过观察，我们可以归纳出规律：

  • 要建造 个梯子，需要 个 | 字符。
  • 要建造 个梯子，需要 个 = 字符。

建立约束条件

我们手头有 个 | 和 个 =。设我们最多能造 个梯子。那么必须满足以下两个条件：

  1. | 字符的数量必须足够：
  2. = 字符的数量必须足够：

从第一个条件可以推导出：。 结合第二个条件 ，为了同时满足两者， 必须小于或等于这两个上限中的较小值。

因此，最大可能的梯子数量 就是：

边界情况

这个公式也优雅地处理了边界情况。

  • 如果 | 的数量不足以搭建一个梯子（即 ），那么 ， 的结果将小于 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()

算法及复杂度

  • 算法：数学/逻辑推导
  • 时间复杂度：。该解法只涉及几次基本的算术和比较操作，与输入大小无关。
  • 空间复杂度：。不需要额外的存储空间。