CF538B Quasi Binary 思维题
题目描述
给出一个数 \(n\)，你需要将 \(n\) 写成若干个数的和，其中每个数的十进制表示中仅包含\(0\)和\(1\)。
问最少需要多少个数
输入输出格式
输入格式：
一行 一个数 \(n(1≤n≤10^6)\)
输出格式：
最少的数的个数，并给出一种方案。
输入输出样例
输入 #1
9
输出 #1
9
1 1 1 1 1 1 1 1 1
输入 #2
32
输出 #2
3
10 11 11
分析
很显然，对于任何一个数，我们把它分成只包含 \(0\) 和 \(1\) 的数字，这样的最小划分数一定不大于 \(9\)
因此在划分的过程中一定不会出现借位的情况
所以我们可以存一下每一位能划分出多少 \(1\)
然后排一下序，从小到大依次计算
分析
#include<cstdio>
#include<algorithm>
const int maxn=15;
struct asd{
int num,id;
asd(){}
asd(int aa,int bb){
num=aa,id=bb;
}
}b[maxn];
bool cmp(asd aa,asd bb){
return aa.num<bb.num;
}
int n,cnt,sta[maxn],top;
int main(){
scanf("%d",&n);
int cs=1;
while(n){
b[++cnt]=asd(n%10,cs);
n/=10;
cs*=10;
}
std::sort(b+1,b+1+cnt,cmp);
int head=1;
while(head<=cnt){
int now=0;
while(b[head].num==0 && head<=cnt) head++;
for(int i=head+1;i<=cnt;i++){
now+=b[i].id;
b[i].num-=b[head].num;
}
now+=b[head].id;
for(int i=1;i<=b[head].num;i++){
sta[++top]=now;
}
b[head].num=0;
}
printf("%d\n",top);
for(int i=1;i<=top;i++){
printf("%d ",sta[i]);
}
printf("\n");
return 0;
}
版权声明：本文为liuchanglc原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。