题目描述
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[]; bool check(long long x, long long k)
{
long long res = ;
while (x)
{
res += x % ;
x /= ;
}
if (res == k)
return true;
return false;
} int main()
{
scanf("%s", s + );
sizee = strlen(s + );
if (s[] == '-')
flg = ;
if (!flg)
{
int tot = ;
for (int i = ; i <= sizee; i++)
if (s[i] == '')
tot++;
if (tot >= sizee - )
flg8 = ;
}
if (sizee == && !flg)
{
if (s[] == '')
printf("-19\n");
else
printf("%c", s[] + );
}
else
if (sizee <= )
{
long long num = , k = ;
if (!flg)
{
for (int i = ; i <= sizee; i++)
{
num = num * + s[i] - '';
k += s[i] - '';
}
}
else
{
for (int i = ; i <= sizee; i++)
{
num = num * + s[i] - '';
k += s[i] - '';
}
num = -num;
}
if (num == -)
printf("-1999999");
else
{
while ()
{
num--;
if (check(abs(num), k + ))
{
printf("%lld\n", num);
break;
}
}
}
}
else
if (flg8 && !flg)
{
s[sizee]++;
s[sizee - ]++;
s[sizee - ]--;
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
else
{
if (flg)
{
for (int i = sizee; i >= ; i--)
{
if (s[i] != '')
{
flag = ;
s[i]++;
break;
}
}
if (flag)
{
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
else
{
printf("-1");
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
}
else
{
//
int sum = ;
for (int i = sizee; i >= ; i--)
{
if (s[i] >= '' && sum >= )
{
s[i]--;
sum = ;
for (int j = i + ; j <= sizee; j++)
{
while (sum && s[j] < '')
{
sum--;
s[j]++;
}
}
int cnt = ;
for (int j = i + ; j <= sizee; j++)
cnt += s[j] - '';
for (int j = i + ; j <= sizee; j++)
{
if (cnt >= )
{
s[j] = '';
cnt -= ;
}
else
{
s[j] = cnt + '';
cnt = ;
}
}
flag = ;
break;
}
sum += '' - s[i];
}
if (flag)
{
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
//
else
{
if (s[] != '')
{
s[]++;
printf("-");
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
else
{
printf("-1");
for (int i = ; i <= sizee; i++)
printf("%c", s[i]);
printf("\n");
}
}
}
}
return ;
}