20

CF538B Quasi Binary 思维题

 3 years ago
source link: http://www.cnblogs.com/liuchanglc/p/13776224.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

题目描述

给出一个数 \(n\) ，你需要将 \(n\) 写成若干个数的和，其中每个数的十进制表示中仅包含 \(0\) 和 \(1\) 。

问最少需要多少个数

输入输出格式

输入格式：

一行 一个数 \(n(1≤n≤10^6)\)

输出格式：

最少的数的个数，并给出一种方案。

输入输出样例

输入 #1

9

输出 #1

输入 #2

32

输出 #2

分析

很显然，对于任何一个数，我们把它分成只包含 \(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;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK