洛谷 P5020 货币系统
题目描述
在网友的国度中共有$ n $种不同面额的货币，第 i种货币的面额为 (a[i])，你可以假设每一种货币都有无穷多张。为了方便，我们把货币种数为(n)、面额数组为 (a[1..n])的货币系统记作$ (n,a)$。
在一个完善的货币系统中，每一个非负整数的金额 (x) 都应该可以被表示出，即对每一个非负整数 (x)，都存在 (n) 个非负整数(t[i])满足 (a[i] imes t[i]) 的和为$ x$。然而， 在网友的国度中，货币系统可能是不完善的，即可能存在金额 (x) 不能被该货币系统表示出。例如在货币系统 (n=3),(a=[2,5,9])中，金额(1,3) 就无法被表示出来。
两个货币系统$ (n,a)$和 ((m,b)) 是等价的，当且仅当对于任意非负整数 (x)，它要么均可以被两个货币系统表出，要么不能被其中任何一个表出。
现在网友们打算简化一下货币系统。他们希望找到一个货币系统 ((m,b))，满足$(m,b) $与原来的货币系统 $(n,a) $等价，且 (m) 尽可能的小。他们希望你来协助完成这个艰巨的任务：找到最小的 (m)。
输入输出格式
输入格式：
输入文件的第一行包含一个整数 (T)，表示数据的组数。
接下来按照如下格式分别给出 (T) 组数据。 每组数据的第一行包含一个正整数 (n)。接下来一行包含 (n) 个由空格隔开的正整数 (a[i])。
输出格式：
输出文件共有 (T)行，对于每组数据，输出一行一个正整数，表示所有与$(n,a) $等价的货币系统 ((m,b))中，最小的 (m)。
输入输出样例
输入样例#1：
2
4
3 19 10 6
5
11 29 13 19 17
输出样例#1：
2
5
说明
在第一组数据中，货币系统$ (2, [3,10])$和给出的货币系统 $(n,a) $等价，并可以验证不存在 $m < 2 $的等价的货币系统，因此答案为 (2)。 在第二组数据中，可以验证不存在(m<n) 的等价的货币系统，因此答案为$ 5$。
【数据范围与约定】
对于(100%)的数据，满足(1 ≤ T ≤ 20), (n),(a[i] ≥ 1)。
思路
先解释一下样例1中第一组数据的3,10,19,6等价于3,10的原因
6=3+3,19=3+3+3+10
即13，19都可以被凑出来
而第二组中的5个数都不能将其他的数凑出来（或被凑出来）
所以直接输出了5
所以就排序看看能不能凑出来就好啦
a[i]=0表示没有i这个数，a[i]=1表示可以凑出i这个数，a[i]=2表示本身就有i这个数
如果处理完成之后a[1~n]中还有等于2的（即本身就有这个数并且不能凑（只能他凑别人））
就让ans++，最后输出就好了
代码
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#include<stack>
#include<deque>
#define INF 0x3f3f3f3f
using namespace std;
int a[25001];
int b[101];
int t,n,ans=0;
inline int read() {
char c=getchar();
int x=0,f=1;
while(c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while(c>='0'&&c<='9')x=x*10+c-48,c=getchar();
return x*f;
}
int main() {
//freopen("money.in","r",stdin);
//freopen("money.out","w",stdout);
t=read();
while (t--) {
ans=0;
memset(a,0,sizeof(a));
scanf("%d",&n);
for (int i=1; i<=n; i++) {
b[i]=read();
a[b[i]]=2;//本身就有b[i]这个数;
}
sort(b+1,b+1+n);//从小到大排序
for (int i=1; i<=b[n]; i++) {
if(a[i]>0) {//如果可以凑出i
//那么也可以凑出i+b[j]
for(int j=1; j<=n; j++) {
if(i+b[j]<=b[n])//排序之后，b[n]一定是b数组中最大的数，在这里防止越界
a[i+b[j]]=1;
else break;//越界的话直接退出
}
}
}
for(int i=1; i<=b[n]; i++)
if(a[i]==2) ans++;//统计a[i]==2的个数输出
printf("%d
",ans);
}
}