牛客网拼多多面试题:
多多君最近在研究某种数字组合:
定义为:每个数字的十进制表示中(0~9),每个数位各不相同且各个数位之和等于N。
满足条件的数字可能很多,找到其中的最小值即可。
多多君还有很多研究课题,于是多多君找到了你--未来的计算机科学家寻求帮助。
共一行,一个正整数N,如题意所示,表示组合中数字不同数位之和。 (1 <= N <= 1,000)
共一行,一个整数,表示该组合中的最小值。 如果组合中没有任何符合条件的数字,那么输出-1即可。
5
5
12
39
50
-1
没有符合条件的数字 (T▽T) ------------------------- 解析:题目45以下就会有重复即1+2+3+4+5+6+7+8+9;保证最小即按照最大在低位进行计算。 代码如下:
#include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #include<map> using namespace std; int main() { int n; scanf("%d", &n); if (n > 45) { printf("-1\n"); return 0; } int ans[20], cnt = 0, pp = 9; map<int, int> mp; while(n != 0) { if (mp[pp] == 0 && n >= pp) { ans[cnt] = pp; mp[pp] = 1; n = n - pp; cnt++; } pp--; } for (int i = cnt-1; i >= 0; i--) { printf("%d", ans[i]); } printf("\n"); return 0; }