货币系统
2022/8/28 23:26:44
本文主要是介绍货币系统,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
P5020 [NOIP2018 提高组] 货币系统 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
- 用筛法,把原有的货币标为2,然后从小到大筛,如果对于某面额是存在的(大于0),那么用该面额加上所有系统中原有的面额所得的面额必定是存在的,这个和可能是原系统中的面额,可能是原来不能凑出来的都标记为可以凑出的(标为1),最后再遍历所有面额1到coin【n】,如果其标记是2那么说明这个面额是必需的
#include <bits/stdc++.h> using namespace std; #define N 1e5 #define INF 2e9 #define MAX 10000000 https://www.luogu.com.cn/problem/P5020 int t, n; int flag[MAX], coin[MAX]; int main() { cin >> t; while (t--) { memset(flag, 0, sizeof(flag)); memset(coin, 0, sizeof(coin)); cin >> n; for (int i = 1; i <= n; i++) { scanf("%d", coin + i); flag[coin[i]] = 2; } sort(coin + 1, coin + n + 1); for (int i = 1; i <= coin[n]; i++) if (flag[i]) for (int j = 1; j <= n; j++) if (i + coin[j] <= coin[n]) flag[i + coin[j]] = 1; else break; int ans = 0; for (int i = 1; i <= coin[n]; i++) { if (flag[i] == 2) ans++; } printf("%d\n", ans); } }
这篇关于货币系统的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-15JavaMailSender是什么,怎么使用?-icode9专业技术文章分享
- 2024-11-15JWT 用户校验学习:从入门到实践
- 2024-11-15Nest学习:新手入门全面指南
- 2024-11-15RestfulAPI学习:新手入门指南
- 2024-11-15Server Component学习:入门教程与实践指南
- 2024-11-15动态路由入门:新手必读指南
- 2024-11-15JWT 用户校验入门:轻松掌握JWT认证基础
- 2024-11-15Nest后端开发入门指南
- 2024-11-15Nest后端开发入门教程
- 2024-11-15RestfulAPI入门:新手快速上手指南