货币系统
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-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门:从零开始的编程之旅
- 2024-11-23Java创业入门:新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门:初学者的简单教程
- 2024-11-23JAVA副业入门:初学者的实战指南