e294: APCS 類似題 - 小崴的新發現 - Zerojudge - 解題紀錄

題目連結: https://zerojudge.tw/ShowProblem?problemid=e294

# 解題思路

本題為求最接近此數的完全奇數
因此有 2 種情況，一個比此數大，一個比此數小，就把這兩個數求出來，再比較它們距離 N 的距離何者最小，這 2 數的求法:

大數：就從左自右掃，掃到某位數為偶數，把此位數加 1 (因為最小偶數為 8, 加 1 變 9, 所以沒進位問題), 此位數之後的數都為 1, 則此數比 N 大的最小值
ex. 134567 => 13(4+1)111
ex. 13256 -> 13(2+1)11 -> 13311
小數：就從左自右掃，掃到某位數為偶數，把此位數減 1 (因為最小偶數為 0, 扣 1 之後要向前一位借位)。此位數假設為最後一位，且前面所有數都為 1, 就要借到最前位，此位數之後都為 9, 則此數比 N 小的最大值
(借位小技巧：如果向前借的那位是奇數，就直接減 2)
ex. 111111102 -> 1111111(0-1)9 -> 向前借 999999(9)9
ex. 35001 -> 3[5-2](0-1)99 -> 3[3](9)99
ex. 13256 -> 13(2-1)99 -> 13199

	#include <iostream>
	#include <cstring>
	using namespace std;

	int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	string s;
	int a[20] = {};
	long long N, bigger, smaller;
	while (cin >> s){
	int len = s.size();
	N = 0;
	for (int i=0; i<len; i++){
	N *= 10;
	N += s[i] - '0';
	}
	memset(a, 0, sizeof(a));
	for (int i=0; i<len; i++){
	int x = (s[i] - '0');
	if (x % 2 == 0){
	a[i] = x + 1;
	for (int j=i+1; j<len; j++) a[j]=1;
	break;
	} else {
	a[i] = x;
	}
	}
	bigger = 0;
	for (int i=0; i<len; i++){
	bigger *= 10;
	bigger += a[i];
	}

	memset(a, 0, sizeof(a));
	for (int i=0; i<len; i++){
	int x = (s[i] - '0');
	if (x % 2 == 0){
	if (x == 0) {
	a[i] = 9;
	int idx = i - 1; // 向前借
	while (idx > 0 && a[idx] == 1){ // 如果向前借的那位是 1
	a[idx] = 9; // 就再借一次
	idx--;
	}
	a[idx] -= 2; // 要記得減 2 成奇數喔
	if (a[idx] < 0) a[idx] = 0;
	} else {
	a[i] = x - 1; // 不用借位，就直接減一就好
	}
	for (int j=i+1; j<len; j++) a[j]=9; // 借位完畢，後面是要全變成九的喔
	break;
	} else {
	a[i] = x;// 本是奇數
	}
	}
	smaller = 0;
	for (int i=0; i<len; i++){
	smaller *= 10;
	smaller += a[i];
	}
	cout << min(bigger - N, N - smaller) << '\n';
	}
	return 0;
	}