http://acm.uestc.edu.cn/#/contest/show/54
F - Fabricate equation
Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)
Submit Status
Given an integer Y, you need to find the minimal integer K so that there exists a X satisfying X−Y=Z(Z≥0) and the number of different digit between X and Z is K under decimal system.
For example: Y=1, you can find a X=100 so that Z=99 and K is 3 due to 1≠0 and 0≠9. But for minimization, we should let X=1 so that Z=0 and K can just be 1.
Input
Only one integer Y(0≤Y≤1018).
Output
The minimal K.
Sample input and output
| Sample Input | Sample Output |
|---|---|
1 |
1 |
191 |
2 |
思路：贪心。倒着扫描，遇到0就忽略，因为对应被减数的该位也设0就好；遇到9，这个特殊，因为比如290-191=99，后面进位后，9这个位也可以使得被减数与结果的该位相同，这样的情况需要两个条件：必须后面可以进位。假如减数那位为0，不论结果为什么，都无法产生进位。第二个条件是，被减数的前一位可以借位，也就是说9这种情况完成后，即便前面遇到减数那位为0，也不能再忽略，只能当一般情况处理。一般情况自然就是k++。
官方题解：
代码：
#include <fstream>
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <vector> using namespace std; #define PI acos(-1.0)
#define EPS 1e-10
#define lll __int64
#define ll long long
#define INF 0x7fffffff char c[]; int main(){
//freopen("D:\\input.in","r",stdin);
//freopen("D:\\output.out","w",stdout);
scanf("%s",c+);
int l=strlen(c+),k=;
c[l+]='';c[]='';
for(int i=l;i>;i--){
if(c[i]=='') continue;
if(c[i]==''){
if(c[i+]==''){
k++;
continue;
}else{
if(c[i-]=='') c[i-]++;//把前面的0毁掉
continue;
}
}else{
k++;
}
}
if(c[]!='') k++;
printf("%d\n",k);
return ;
}