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;
}