【每日一题】Quasi Binary

题目

如果数字的十进制表示形式仅包含数字 0 或 1，则称为 quasibinary。例如，数字 0、1、101、10011 是 quasibinary，而数字 12、900 不是。
给定一个正整数 n（1 ≤ n ≤ 10⁶）。将其表示为 quasibinary 的总和，且 quasibinary 的个数最少。

解题思路

先求出 n 的每位数字，记录在 vec 中。

遍历 vec，如果某位数字大于 0，那么这个位数可以分出一个 1 出来，计入 num 中；否则分出一个 0 出来，计入 num 中。

遍历完成后，保存 num。如果此时 num = 0，表示 vec 中的数字均为 0，整数 n 分割完毕。

C++代码

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int n;
    cin >> n;
    vector<int> vec;
    while(n){
        vec.push_back(n%10);
        n /= 10;
    }

    vector<int> ans;
    while(1){
        int num = 0;
        for(int i=vec.size()-1; i>=0; --i){
            num *= 10;
            if(vec[i]>0){
                num += 1;
                vec[i] -= 1;
            }
        }
        if(num > 0)
            ans.push_back(num);
        else
            break;
    }

    cout << ans.size() << endl;
    for(int i=0; i<ans.size(); ++i)
        cout << ans[i] << " ";
    cout << endl;
    return 0;
}