首页 > 代码库 > codeforces 489C.Given Length and Sum of Digits... 解题报告
codeforces 489C.Given Length and Sum of Digits... 解题报告
题目链接：http://codeforces.com/problemset/problem/489/C
题目意思：给出 m 和 s，需要构造最大和最小的数。满足长度都为 m，每一位的数字之和等于 s。如果构造不出来，输出 -1 -1。否则输出最小和最大且符合条件的数。
想了两个多小时，发现想错了方向......
/******************************************
首先把不能得到最小数和最大数的情况揪出来。
第二组测试数据 3 0 有提示，s = 0 且 m > 1，
还有一种无解的情况就是 9 m < s（怎么填全部位的数字之和都凑不够 s），其实这种情况是有最小解的，前提是s >= 1，10000000....0 就是了，但是都归为 -1 -1 行列（感觉这个不是太过严谨）。
至于 s = 0，m = 1是 输出 0 0。然后就开始重头戏了........
我是从最小数开始构造的（感觉这样做就呵呵了），容易知道最小数的构造是，从个位开始填数，尽量填最大的数字9，然后剩下的数remain = s - 9，接着填十位、百位、......直到填完 第 m 位。我们要尽可能把最大的数字往低位填，那么才能保证最终得到的数是最小的。但是要考虑到填的过程中，有可能这个remain 不足9，然后尝试8，再不行的话，填7，直到0，不过前提是保证最高位最小为 1，保证没有前导 0 嘛。
但实现起来很复杂，循环是从 m-1 ——> 0 的，于是要考虑 i == 1 时，不能把remain完全填光，只能填remain + 1。对于第一组数据 2 15，ans：69 96；好像又要额外讨论......所以总体来讲，不好写，即使写出来也很烦琐。
******************************************/
看了别人的，一下子顿悟了！
从最大数开始构造就简单多了。循环变成 0 ~ m-1，然后死命填大数字9，不行的话填剩下最大的，之后的位就是填0了。
构造最小数更加方便，把最大数复制到最小数里，然后颠倒过来，如果首位是 0，就找到后面位中第一次遇到的非0数字，从它那里拿1，这位数就减1，就是答案了。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <algorithm> 6 using namespace std; 7 8 int main() 9 {10 #ifndef ONLINE_JUDGE11 freopen("in.txt", "r", stdin);12 #endif13 int m, s;14 while (scanf("%d%d", &m, &s) != EOF)15 {16 if (m == 1 && s == 0)17 printf("0 0\n");18 else if (s == 0 || 9*m < s)19 printf("-1 -1\n");20 else21 {22 string s1, s2;23 for (int i = 0; i < m; i++)24 {25 int x = min(9, s);26 s -= x;27 s2 += char(x + ‘0‘);28 }29 s1 = s2;30 reverse(s1.begin(), s1.end());31 bool flag = false;32 for (int i = 0; i < m && !flag; i++)33 {34 if (s1[i] == ‘0‘)35 {36 for (int j = i+1; j < m && !flag; j++)37 {38 if (s1[j] != ‘0‘)39 {40 s1[j]--;41 s1[i]++;42 flag = true;43 break;44 }45 }46 }47 }48 cout << s1 << " " << s2 << endl;49 }50 }51 return 0;52 }
codeforces 489C.Given Length and Sum of Digits... 解题报告