2021.01.25包子凑数
2022/3/19 6:29:48
本文主要是介绍2021.01.25包子凑数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
2021.01.25包子凑数
题目描述
有n种蒸笼,每种有无限个,且每种可以蒸Ai个包子,问有多少种包子个数是蒸不出来的。如果有无限多个,输出INF。
输入格式
第一行包含一个整数N。(1 <= N <= 100)
以下N行每行包含一个整数Ai。(1 <= Ai <= 100)
输出格式
一个整数代表答案。如果凑不出的数目有无限多个,输出INF。
样例输入
2
4
5
样例输出
6
样例输入
2
4
6
样例输出
INF
知识扩展
- 扩展欧几里得算法:如果n个数不是互质的,则它们凑不出来的数有无数个。
- gcd函数
思路
- 首先判断是否有无限多个数不能凑出
- 如果存在有限个数不能被凑出,则通过动态规划算出1-100000中不能被凑出的数字。即可得出所有结果。(通过模拟一些例子可以得出往后的数字都是可以被凑出的。)
注意:选择100000长度不是必然的,可以选择更长的数字。经实验验证,对于蓝桥杯测评系统,一维dp对多可设置成10^7。
此外,如果有三个数互质,如19,17,5则这组数不能凑出的数中最大的为n,而19,17不能凑出的最大数为m,则m≥n
代码
int n; int[] arr; int[] dp = new int[10010]; //最多可以10^7 void test() { //如果一组数是互质的,那么他们凑不出来的数有有限个,即当n足够大时,n可以被凑出 Scanner cin = new Scanner(System.in); n = cin.nextInt(); arr = new int[n]; for(int i = 0; i < n; i++) arr[i] = cin.nextInt(); Arrays.sort(arr); if(arr[0] == 1) { //如果可以单独蒸1个 System.out.println(0); return; } //判断他们是否互质 int gcd = arr[0]; for(int i = 1; i< arr.length; i++) gcd = Gcd(gcd,arr[i]); if(gcd!=1) { //他们不是互质的 System.out.println("INF"); return; } //有限个数字可以被凑出 for(int i = 0; i < arr.length; i++) { dp[arr[i]] = 1; for(int j = arr[i]; j < dp.length; j++) { if(dp[j-arr[i]] == 1) dp[j] = 1; //转移方程 } } //计数 int cnt = 0; for(int i = 1; i < dp.length; i++) if(dp[i] == 0) cnt++; System.out.println(cnt); } int Gcd(int a, int b) { if(a % b == 0) return b; else return Gcd(b,a%b); }
这篇关于2021.01.25包子凑数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?
- 2024-05-30java excel上传--poi
- 2024-05-30安装笔记本应用商店的pycharm,再安排pandas等模块,说是没有打包工具?
- 2024-05-29java11新特性