CF538B Quasi Binary 思维题

• 2020 年 10 月 7 日
• 筆記
• 思维题

题目描述

给出一个数 \(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;
}