a151 - Error
題目描述
題目要求找出一個數字 x，使得從 1 到 x 的所有數字的位數總和等於輸入數字 n。如果找不到這樣的 x，則輸出 -1。
解題思路
這題可以使用二分搜尋法來找到答案。由於位數總和與數字大小之間存在單調性，我們可以利用二分搜尋來縮小搜尋範圍。
首先，計算從 1 到 n/2 的位數總和，如果這個總和過小，則在 n/2 到 n 之間搜尋，反之則在 1 到 n/2 之間搜尋。
在二分搜尋的過程中，我們需要計算從 1 到 mid 的位數總和。
計算位數總和的過程可以通過迭代來實現，每次迭代將數字的每一位加到總和中，然後將數字除以 10。
複雜度分析
- 時間複雜度: O(log(n) * log(n))。二分搜尋的次數為 O(log(n))，每次計算位數總和的次數為 O(log(n))。
- 空間複雜度: O(1)。
程式碼
#include <iostream>
using namespace std;
long long int bs(long long int min,long long int max,long long int n){
long long int all=0,sum=n,m=(min+max)/2;
if(max<min)
return m;
for(;n>m&&n>9;){
n-=m;
all+=m;
n-=n/10;
}
all+=n;
if(all*2>=sum)
return bs(min,m-1,sum);
return bs(m+1,max,sum);
}
int main(){
long long int n;
while(cin >> n)
cout << bs(1,n/2,n)+1 << "\n";
}