侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 551 篇文章
  • 累计创建 117 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2023-01-14 / 0 评论 / 0 点赞 / 13 阅读 / 626 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2023-01-14,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

卡片 - 蓝桥云课


问题描述

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

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

输入格式

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

输出格式

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

样例输入

6

样例输出

3

样例说明

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

评测用例规模与约定

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

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

运行限制

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

解题

方法一:找规律 二分查找

思路

首先我们暴力枚举 1301 \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

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

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

代码

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);
    }
}
0

评论区