Day2：精简钱箱 题解
2026-08-13 20:47:18
发布于：浙江
5阅读
0回复
0点赞
原题链接：T118313.精简钱箱
思路详解：将输入数据从小到大排序后，遍历1~25000 ，标记每个数字是否能通过目前手上面额实现，若无法实现且可获得该面值货币，将该面值货币加入手中，并继续遍历。遍历结束后，统计获得过多少次货币，输出答案。
关键代码部分展示：
sort(a.begin(),a.end()); //对输入排序
bitset<25005> vis; //统计该数字是否可以通过手上已有面额组合得到
int l=2;
ll ans=1; //答案
in.push_back(a[1]); //由于开始时手上没有货币，因此必须获得最小面额那张（最小面额货币无法被大面额货币替代）
vis[a[1]]=1;
for(int i=a[1]+1;i<=mx;i++){
for(auto it:in){
if(vis[i-it]) vis[i]=1; //判断该面额是否可以被获得
}
if(vis[i]&&i==a[l]) l++; //若可获得，那直接跳到下一张
else if(i==a[l]){ //若不可获得
ans++; //答案计数增加
in.push_back(a[l]); //加入手中
l++;
vis[i]=1; //标记
}
}
答案展示：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int main(){
int _;
cin>>_;
while(_--){
int n,mx=-1e9;
cin>>n;
vector<int> a(n+1,0);
vector<int> in;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(mx,a[i]);
}
sort(a.begin(),a.end());
bitset<25005> vis;
int l=2;
ll ans=1;
in.push_back(a[1]);
vis[a[1]]=1;
for(int i=a[1]+1;i<=mx;i++){
for(auto it:in){
if(vis[i-it]) vis[i]=1;
}
if(vis[i]&&i==a[l]) l++;
else if(i==a[l]){
ans++;
in.push_back(a[l]);
l++;
vis[i]=1;
}
}
cout<<ans<<endl;
}
return 0;
}
这里空空如也
有帮助，赞一个