蓝桥杯：卡片 (编程题)
题目链接
问题描述
输入格式
输出格式
输入输出样例
输入样例
输出样例
样例说明
评测用例规模与约定
运行限制
思路分析：
AC代码（Java）：
问题描述
小蓝有 k 种卡片, 一个班有 n 位同学, 小蓝给每位同学发了两张卡片, 一 位同学的两张卡片可能是同一种, 也可能是不同种, 两张卡片没有顺序。没有 两位同学的卡片都是一样的。
给定 n, 请问小蓝的卡片至少有多少种?
输入格式
输入一行包含一个正整数表示 n 。
输出格式
输出一行包含一个整数, 表示答案。
输入输出样例
输入样例
6输出样例
3样例说明
小朋友们手中的卡片可能是: (1,1),(1,2),(1,3),(2,2),(2,3),(3,3) 。
评测用例规模与约定
对于 50% 的评测用例, 1≤n≤10^4 。
对于所有评测用例, 1≤n≤10^9 。
运行限制
- 最大运行时间：1s
- 最大运行内存: 256M
思路分析：
一开始没注意n的规模，直接暴力模拟，key和value。
模拟的思路是，当value=1的时候，只能组合成1-1，那么value就提升到2，然后就可以组合成1-1，1-2，2-1，2-2，当value提升到3,key重置为1，继续模拟：1-1,1-2,1-3,2-1,2-2,2-3,3-3，直接使用set去重即可。
结果啪的一下，很快啊，只过了50%，其余部分超时了。
超时代码：
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
//至少有多少种，所以求出n位同学可能拿到的卡片数量的组合,从1-1，开始，判断长度是否满足，不满足就变成1-2,2-2,1-3,2-3,3-3
int key = 1;
int value = 1;
Set<String> set = new HashSet<>();
while(set.size()<n){
set.add(key+","+value);
if(key<value){
key++;
}else{
key = 1;
value++;
}
}
//取出set，判断一共有多少个数字
Set<Integer> nums = new HashSet<>();
for(String str : set){
//切割一下
String[] strs = str.split(",");
nums.add( Integer.parseInt( strs[0] ) );
nums.add( Integer.parseInt( strs[1] ) );
}
System.out.println( nums.size() );
scan.close();
}
}然后看n的范围，10^9次方，如果要模拟所有子串，会到O(n^2)，绝对超时，所以暴力模拟行不通。
然后换一种思路，可不可以找一下规律呢？即当n=1的时候，k=1，n=2的时候，k=2。
所以直接复制了上面的代码，写了个for，判断n从1-100之间的结果，看看有没有规律。
public static void main(String[] args) {
for(int n = 1;n<100;n++){
//至少有多少种，所以求出n位同学可能拿到的卡片数量的组合,从1-1，开始，判断长度是否满足，不满足就变成1-2,2-2,1-3,2-3,3-3
int key = 1;
int value = 1;
Set<String> set = new HashSet<>();
while(set.size()<n){
set.add(key+","+value);
if(key<value){
key++;
}else{
key = 1;
value++;
}
}
//取出set，判断一共有多少个数字
Set<Integer> nums = new HashSet<>();
for(String str : set){
//切割一下
String[] strs = str.split(",");
nums.add( Integer.parseInt( strs[0] ) );
nums.add( Integer.parseInt( strs[1] ) );
}
System.out.println( "n:"+n+",size:"+nums.size() );
}
}跑一下程序，出结果一看，果然是可以找规律的。
n:1,size:1
n:2,size:2
n:3,size:2
n:4,size:3
n:5,size:3
n:6,size:3
n:7,size:4
n:8,size:4
n:9,size:4
n:10,size:4
n:11,size:5
n:12,size:5
n:13,size:5
n:14,size:5
n:15,size:5
n:16,size:6
n:17,size:6
n:18,size:6
n:19,size:6
n:20,size:6
n:21,size:6
n:22,size:7
n:23,size:7
n:24,size:7
n:25,size:7
n:26,size:7
n:27,size:7
n:28,size:7
n:29,size:8
n:30,size:8
n:31,size:8
n:32,size:8
n:33,size:8
n:34,size:8
n:35,size:8
n:36,size:8
n:37,size:9
n:38,size:9
n:39,size:9
n:40,size:9
n:41,size:9
n:42,size:9
n:43,size:9
n:44,size:9
n:45,size:9
n:46,size:10
n:47,size:10
n:48,size:10
n:49,size:10
n:50,size:10
n:51,size:10
n:52,size:10
n:53,size:10
n:54,size:10
n:55,size:10
用n和k来替代，我们不难看出，k的出现规律是和自身数字有关的。
- 比如k是1，就只出现1次，也就是n=1的时候，k=1.
- k是2，就出现2次，也就是n=2和n=3的时候，k都是2。
- k是3，就出现3次，也就是n=4，n=5，b=6的时候，k都是3.
- 以此类推。
也就是说，我们可以直接拿到n，然后进行判断，如果k=1的时候，我们就让n-1，k=2的时候，我们就让n-2，k=3的时候，我们就让n-3..……。这样，当n<=0的时候，我们的k就得到了。
AC代码（Java）：
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改
public class Main {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n = scan.nextInt();
int k = 0;
//穷举之后发现了规律
while(n>0) {
k++;
n -= k;
}
//循环出来的k就是结果
System.out.println(k);
scan.close();
}
}