URAL 1727. Znaika's Magic Numbers（数学 vector）

主题链接：http://acm.timus.ru/problem.aspx?space=1&num=1727

1727. Znaika‘s Magic Numbers

17

3
7 12 43

代码例如以下：

#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 100017;
vector<int> vv[maxn];
int vis[maxn], ans[maxn];
void init()
{
    for(int i = 1; i < maxn; i++)
    {
        int tt = i;
        int sum = 0;
        while(tt)
        {
            sum+=tt%10;
            tt/=10;
        }
        vv[sum].push_back(i);
    }
}
int main()
{
    int n;
    init();
    while(~scanf("%d",&n))
    {
        memset(vis, 0, sizeof(vis));
        int k = 0;
        for(int i = 45; i > 0; i--)
        {
            if(n >= i)
            {
                for(int j = 0; j < vv[i].size(); j++)
                {
                    if(n < i)
                        break;
                    if(vis[vv[i][j]] == 0)
                    {
                        vis[vv[i][j]] = 1;
                        ans[k++] = vv[i][j];
                        n-=i;
                    }
                }
            }
            if(n <= 0)
                break;
        }
        if(k==0 || n != 0)
        {
            printf("-1\n");
            continue;
        }
        printf("%d\n%d",k,ans[0]);
        for(int i = 1; i < k; i++)
        {
            printf(" %d",ans[i]);
        }
        printf("\n");
    }
    return 0;
}