题目描述
LYK拥有一个十进制的数N。它赋予了N一个新的意义：不考虑N的符号，将N每一位都拆开来后再加起来就是N所拥有的价值。例如数字123拥有6的价值，数字999拥有27的价值，数字-233拥有8的价值。
假设数字N的价值是K，LYK想找到一个价值是K+1的数字，当然这个答案实在太多了，LYK想使得这个价值为K+1的数字尽可能大，并且需要保证这个数字小于N。
输入格式(bit.in)
一个整数N。
输出格式(bit.out)
一个数表示答案。你需要输出一个整数，且这个数不包含前导0。
输入样例1
199
输出样例1
-299
输入样例2
1520
输出样例2
1512
对于20%的数据|N|<=10
对于40%的数据|N|<=100
对于60%的数据|N|<=10^9
对于80%的数据|N|<=10^1000
对于100%的数据|N|<=10^100000。
分析：其实就是一道比较恶心的讨论题.如果|N| <= 100000（甚至可以更大），可以暴搜。如果N是负数，从后往前第一位不是9的数上+1，如果N不是负数，那么肯定存在一个第i位，第i位上的数-1,第i位后面的数分摊+2，再把后面的数重新组合一下，把尽量多的数分摊在前面的位上。如果不存在这么一个第i位，那么最后输出的肯定是一个负数，第一位++，添上负号就可以了.如果第一位是9，就在前面补上1，总之就是非常非常麻烦的讨论，我在考场上写了一个骗分程序，结果范围看错了，数组开小了只得了60分QAQ.
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; int sizee; bool flag = false, flg = false, flg8 = false; char s[1001000]; bool check(long long x, long long k) { long long res = 0; while (x) { res += x % 10; x /= 10; } if (res == k) return true; return false; } int main() { scanf("%s", s + 1); sizee = strlen(s + 1); if (s[1] == '-') flg = 1; if (!flg) { int tot = 0; for (int i = 1; i <= sizee; i++) if (s[i] == '8') tot++; if (tot >= sizee - 1) flg8 = 1; } if (sizee == 1 && !flg) { if (s[1] == '9') printf("-19 "); else printf("%c", s[1] + 1); } else if (sizee <= 7) { long long num = 0, k = 0; if (!flg) { for (int i = 1; i <= sizee; i++) { num = num * 10 + s[i] - '0'; k += s[i] - '0'; } } else { for (int i = 2; i <= sizee; i++) { num = num * 10 + s[i] - '0'; k += s[i] - '0'; } num = -num; } if (num == -999999) printf("-1999999"); else { while (1) { num--; if (check(abs(num), k + 1)) { printf("%lld ", num); break; } } } } else if (flg8 && !flg) { s[sizee]++; s[sizee - 1]++; s[sizee - 2]--; for (int i = 1; i <= sizee; i++) printf("%c", s[i]); printf(" "); } else { if (flg) { for (int i = sizee; i >= 2; i--) { if (s[i] != '9') { flag = 1; s[i]++; break; } } if (flag) { for (int i = 1; i <= sizee; i++) printf("%c", s[i]); printf(" "); } else { printf("-1"); for (int i = 2; i <= sizee; i++) printf("%c", s[i]); printf(" "); } } else { // int sum = 0; for (int i = sizee; i >= 1; i--) { if (s[i] >= '1' && sum >= 2) { s[i]--; sum = 2; for (int j = i + 1; j <= sizee; j++) { while (sum && s[j] < '9') { sum--; s[j]++; } } int cnt = 0; for (int j = i + 1; j <= sizee; j++) cnt += s[j] - '0'; for (int j = i + 1; j <= sizee; j++) { if (cnt >= 9) { s[j] = '9'; cnt -= 9; } else { s[j] = cnt + '0'; cnt = 0; } } flag = 1; break; } sum += '9' - s[i]; } if (flag) { for (int i = 1; i <= sizee; i++) printf("%c", s[i]); printf(" "); } // else { if (s[1] != '9') { s[1]++; printf("-"); for (int i = 1; i <= sizee; i++) printf("%c", s[i]); printf(" "); } else { printf("-1"); for (int i = 1; i <= sizee; i++) printf("%c", s[i]); printf(" "); } } } } return 0; }