Google kickStart-2018-RoundA-Problem A. Even Digits

本文主要是介绍Google kickStart-2018-RoundA-Problem A. Even Digits，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接

题目大意：

给定一个数N，N中的每一位数都不能是奇数，如果有奇数则改成与它最近的数M（M中的每一个数都是偶数）
比如：N=2018，1是奇数，改成M=2020，11改成8

直接上官方题解(可以直接看Large dataset)：

Even Digits: Analysis.
To make our discussion easier, let us define a beautiful integer as an integer which has only even digits in its decimal representation.

Small dataset

One useful observation for solving this problem is that we either only want to press the minus button or only want to press the plus button. It is useless to have both types in the same sequence, since they cancel each other out.

Therefore, we want to either keep pressing the minus button, or keep pressing the plus button, until we have a beautiful integer. Let M be the minimum number of minus button presses before reaching a beautiful integer, and let P be the minimum number of plus button presses before reaching a beautiful integer. Then the answer is the smaller of M and P.

Note that for this problem, the answer for an input N is bounded above by N, since we can just press the minus button N times to reach the beautiful integer 0. Therefore, since N ≤ 105, we can solve the Small dataset using complete search.

We can loop over a value i in the range [0, N], and, for each i, check whether N+i or N-i is a beautiful integer. If that is the case, then we break the loop and return i as the answer.

Large dataset

Iterating over the range [0, N] would be too slow for this dataset. Therefore, we need another approach. To find the value of M, we must find the largest beautiful integer that is still no greater than N. Let us call this integer X. Similarly, to find the value of P, we can find the smallest beautiful integer that is still no smaller than N. Let us call this integer Y.

We can find X by decreasing the first odd digit in N by one and then replacing all digits to the right of that odd digit with the largest even digit (i.e. 8). For example, if N=4436271, then X=4428888. This can create a leading 0, which we can simply drop the leading 0 in that case. If there are no odd digits in N, then N is a beautiful integer, thus X=N.

By constructing X this way, it is guaranteed that there will be no beautiful integer between X and N, since the next beautiful integer after X would be larger than N at the first odd digit. For the example above, the next beautiful integer after X is 4440000, which is larger than N.

Similarly, we can find Y by increasing the first odd digit in N by one and replacing all digits to the right of that odd digit with the smallest even digit (i.e. 0). If there are no odd digits in N, then N is a beautiful integer, thus Y=N. However, when finding Y, we must watch out for some tricky cases. If the first odd digit is 9, then we must replace the digit directly to the left of that odd digit as well with the next even digit. For example, if N=86912, then Y=88000.

Another tricky case is when the digit directly to the left of the first odd digit is 8. In this case, we must replace the digit directly to the left of that 8 digit as well, and keep doing this until we have a non-8 digit. For example, if N=6488962, then Y=6600000. Finally, if all digits to the left continue to be 8 until we reach the leftmost digit, or if the first digit of N is a 9, then we must add the smallest non-zero even digit (i.e. 2) as a new digit on the left. For example, if N=88892 or N=91112, then Y=200000.

Once we know X and Y, we also know M and P, and we can take the smallest of those values, just as we did before.

代码实现：

#include<cstdio>
#include<sstream>
#include<iostream>
#include<algorithm>using namespace std;#define LL long longLL haveOdd(LL tmp){int left;LL  flag=0;LL  Odd=1;while(tmp!=0){left=tmp%10;tmp/=10;Odd=Odd*10;if(left%2!=0){flag=Odd;}}return flag;
}LL findMiner(LL n){/// 比n小的全部非奇数数：奇数左边的第一个数减一，后面的全是8：4436271 -> 4428888LL tmpFlag=haveOdd(n);if(tmpFlag!=0){tmpFlag/=10;n=n/tmpFlag;n=n*tmpFlag;n=n-tmpFlag;while(tmpFlag>0){tmpFlag/=10;n=n+8*tmpFlag;}}return n;
}LL findBigger(LL n){/** 比n大的全部非奇数数：最左边的第一个奇数加1，后面的全是0，4436271 -> 4440000若奇数左侧第一个数是8：一直加1直到不是8为止（题解中好像是直接替换8）若首字符是8、9的数字特殊处理，直接替换成最小的非0偶数作为新数字（这里没判断）: N=88892 or N=91112 ->  200000*/LL tmpFlag=haveOdd(n);if(tmpFlag==0){return n;}if(tmpFlag!=0){tmpFlag=tmpFlag/10;n=n/tmpFlag;n=n*tmpFlag;n+=tmpFlag;n=findBigger(n);}return n;
}int calculate(LL n,int i){LL M,N,ans;M=findMiner(n);//找到比n小的最大 全偶数的数字N=findBigger(n);//找到比n大的最小 全偶数的数字//cout<<"N:"<<N<<endl;//cout<<"M:"<<M<<endl;ans=(n-M)>(N-n)?(N-n):(n-M);cout<<"Case #"<<i<<": "<<ans<<endl;return 0;
}
int main(){//freopen("A.in","r",stdin);//freopen("A.out","w",stdout);int N;LL n;cin>>N;for(int i=1; i<=N; i++){cin>>n;calculate(n,i);}return 0;
}