题目链接：https://code.google.com/codejam/contest/9234486/dashboard#s=p0
给一个数，这个数每次只能+1或-1，问把这个数变成每一位都是偶数的最少步数。
其实就是说，求和这个数的差的绝对值最小的每位都是偶数的数。
考虑比这个数小的数，要最大化这个数就是把这个数最高位的奇数-1后面的数都是8；
考虑比这个数大的数，要最小化这个数就是把这个数最高位的奇数+1后面的数都是0，但是要考虑当前最高位是9的时候，再+1是不可能的了，所以这一个情况就不需要++。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
using namespace std;
using LL = unsigned long long;
const int maxn = 18;
string s;
LL (string x) {
string y = x;
LL a = stoull(x);
y[0]--;
for(int i = 1; i < y.length(); i++) y[i] = '8';
LL b = stoull(y);
return a - b;
}
LL up(string x) {
string y = x;
LL a = stoull(x);
if(y[0] != '9') {
y[0]++;
for(int i = 1; i < y.length(); i++) y[i] = '0';
LL b = stoull(y);
return b - a;
}
}
signed main() {
freopen("in", "r", stdin);
freopen("out", "w", stdout);
int T, _ = 1;
scanf("%d", &T);
while(T--) {
cin >> s;
int n = s.length();
LL ret = 0;
for(int i = 0; i < n; i++) {
if((s[i] - '0') % 2 == 0) continue;
ret = min(down(s.substr(i, n-i)), up(s.substr(i, n-i)));
break;
}
printf("Case #%d: %lldn", _++, ret);
}
return 0;
}
|
近期评论