f348 - 完全偶數
題目描述
題目要求找到離給定正整數 n 最近的「完全偶數」。完全偶數定義為每一位數都是偶數的正整數。輸出最近完全偶數與 n 的距離。
解題思路
程式碼首先預先計算了從 0 到 1000000 之間所有完全偶數，並將結果儲存在布林陣列 a 中。然後，程式碼從 n 開始，向兩個方向搜尋完全偶數：
- 從
n向大方向搜尋，找到第一個完全偶數，計算與n的距離。 - 從
n向小方向搜尋，找到第一個完全偶數，計算與n的距離。 最後，程式碼輸出兩個距離中的最小值。如果n本身就是完全偶數，則距離為 0。如果找不到完全偶數，則輸出 1000000。
複雜度分析
- 時間複雜度: O(n)
- 空間複雜度: O(n)
程式碼
#include <iostream>
using namespace std;
int n,ans;
bool a[1000005];
bool ise(int k){
while(k){
if(k%2)return 0;
k/=10;
}
return 1;
}
int main(){
for(int i=0;i<=1000000;i+=2){
a[i]=ise(i);
}
cin >> n;
for(int i=n;i<=1000000;++i){
if(a[i]){
ans=i-n;
break;
}
}
if(ans==0&&a[n]==0){
ans=1000000;
}
for(int i=n;i>=0;--i){
if(a[i]){
ans=min(ans,n-i);
break;
}
}
cout << ans;
}