【找规律, 二分查找】卡片【蓝桥杯】

题目

卡片 - 蓝桥云课

---

问题描述

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

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

输入格式

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

输出格式

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

样例输入

6

样例输出

3

样例说明

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

评测用例规模与约定

对于 $50 \%$ 的评测用例, $1 \leq n \leq 10^4$ 。

对于所有评测用例, $1 \leq n \leq 10^9$ 。

运行限制

• 最大运行时间：1s
• 最大运行内存: 256M

解题

方法一：找规律 二分查找

思路

首先我们暴力枚举 $1 \sim 30$ 位同学时，卡片的数量有什么规律：

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        for (int n = 1; n <= 30; ++n) {
            for (int i = 1; i <= n; ++i) {
                Set<Set<Integer>> st = new HashSet<>();
                for (int j = 1; j <= i; ++j) {
                    for (int k = 1; k <= i; ++k) {
                        Set<Integer> pr = new HashSet<>();
                        pr.add(j);
                        pr.add(k);
                        st.add(pr);
                    }
                }
                if (st.size() >= n) {
                    System.out.println(n + ": " + i);
                    break;
                }
            }
        }
    }
}

1: 1
2: 2
3: 2
4: 3a
5: 3
6: 3
7: 4
8: 4
9: 4
10: 4
11: 5
12: 5
13: 5
14: 5
15: 5
16: 6
17: 6
18: 6
19: 6
20: 6
21: 6
22: 7
23: 7
24: 7
25: 7
26: 7
27: 7
28: 7
29: 8
30: 8

很明显的发现卡片按照 $x$ 个 $x$ 的规律依次递增。

接下来我们只需要按照这个规律写个二分查找即可（注意二分查找左边界）。

代码

import java.util.*;
import java.io.*;

public class Main {
    static int n;
    static boolean check(int m) {
        int sum = 0;
        for (int i = 1; i <= m; ++i) {
            if ((sum += i) >= n) return true;
        }
        return sum >= n;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        int l = 1, r = n;
        while (l < r) {
            int m = l + r >> 1;
            if (check(m)) r = m;
            else l = m + 1;
        }
        System.out.println(l);
    }
}