目录

题目链接：3.卡片 - 蓝桥云课

题目描述

输入格式

输出格式

样例输入

样例输出

样例说明

评测用例规模与约定

解法一：数学推导

Java写法：

C++写法：

AC情况

时间复杂度和空间复杂度

1. 时间复杂度

2. 空间复杂度

​编辑

总结

---

---

题目链接：3.卡片 - 蓝桥云课

注：下述题目描述和示例均来自蓝桥云客

题目描述

小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。

给定 n, 请问小蓝的卡片至少有多少种?

输入格式

输入一行包含一个正整数表示 n 。

输出格式

输出一行包含一个整数, 表示答案。

样例输入

6

样例输出

3

样例说明

小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。

评测用例规模与约定

对于 50 的评测用例,  。

对于所有评测用例,   。

---

解法一：数学推导

1. ​问题分析：每个同学的卡片组合可以有两种情况：

   • 两张相同的卡片，如 (1, 1)，共有 k 种组合。
   • 两张不同的卡片，如 (1, 2)，共有 种组合（即 种）。

   因此，总组合数为 。我们需要找到最小的 k，使得总组合数至少为 n。

2. ​数学推导：通过解方程  ，可以得到 k 的最小值为向上取整后的结果。

---

Java写法：

import java.util.Scanner;
// 1:无需package
// 2: 类名必须Main, 不可修改

public class Main {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        // 1.k种卡片
        // 2.n位同学
        // 3.每位2张卡片（可能同一种，也可能不同）
        // 4.没有 两位 同学的卡片一样
        // 问：小兰的卡片至少多少种(求解最少满足的条件)?
        int n = scan.nextInt();

        for(int k = 1;k < n; k++){
          if((k*(k-1))/2 >= n - k){
            System.out.println(k);
            break;
          }
        }

        scan.close();
    }
}

C++写法：

#include <iostream>
using namespace std;

int main() {
    int n;
    cin >> n;

    for(int k = 1; k <= n; k++) {
        if( (k * (k - 1) ) / 2 >= (n - k) ) {
            cout << k << endl;
            return 0;
        }
    }

    return 0;
}

AC情况

时间复杂度和空间复杂度

1. 时间复杂度

• 定义：算法执行时间随输入规模 n 的增长趋势，常用大O表示法（如 O(1)、O(n)、O(n²)）。
• 常见场景：
  • C++：
    • 示例：斐波那契递归（O(2ⁿ)） vs 迭代优化（O(n)）。
    • 优化策略：选择高效算法（如快速排序替代冒泡排序）。
  • Java：
    • 示例：遍历数组求最大值（O(n)）。
    • 优化策略：利用JVM的JIT编译提升热点代码性能。

2. 空间复杂度

• 定义：算法运行所需内存空间随 n 的增长趋势。
• 常见场景：
  • C++：
    • 示例：动态数组（new int[n]）的空间复杂度为 O(n)。
    • 风险：递归可能导致栈溢出（如深度递归需 O(n) 空间）。
  • Java：
    • 示例：递归算法的空间复杂度同样为 O(n)（栈帧存储）。
    • 优化：使用迭代替代递归减少栈空间占用。

---

---

---

总结

        推公式推公式啊铁铁