題目意思： 有一個數組 s[1] = 1 , s[2] = 1 2 , .......s[k] = 1....k，要求給定一個n表示數組的第幾位，要求這個第幾位是什麼數。例如 n為1 時候是1 n為 2 時候是1 ，n 為3 時候為2
解題思路： 1:思路：預處理打表+查找
2:題目給的數據可以發現一些規律
s[1]：1 總位數1
s[2]：1 2 總位數1+2 = 3
s[3]：1 2 3 總位數1+2 +3 = 6
.
.
.
s[9]：1 2 3 4 5 6 7 8 9 總位數1+2 +3+...+9 = 45
s[10]: 1 2 3 4 5 6 7 8 9 10 總位數45+1+2 +3+...+9 +1+0 = 56
s[K]：1 2 3 4 . . . . . . k 總位數 num[k-1]+1+2+......
用num[k]保存當值為k時候總的位數.
所以我們要是能夠預先把所有的數據全部求出弄成一張表，然後輸入的時候直接查找位於那個位置，然後在去查找這個位置 ,由於上面的遞增趨勢，我麼可以推斷當k到100000時候就會超過int，所以開個這麼大的數組就可以了。
3:打表過程:我麼采用枚舉當前值的位數，例如位數為1，那麼就有1-9共9位數，如果位數為2就有10-99公共90個.......假設當前的數值為n，那麼根據上面的規律求出num[n]，一次這樣求出所以數據
4:查找，O(n)的時間復雜度，只要找到num[i-1] < n, num[i]>=n , 那麼我們可以知道這個數存在s[n]中,把n減去num[i-1]，可以知道要求的數在s[n]中第幾位，然後再去一一判斷。注意這裡n可能為1234等多位數，那麼要把他拆開，這時候是先拆前面即最大位。
5注意事項:由於這一題的n最大為2147483647，那麼我們開得num數組要為long long，中間的一些處理也要為long long不然會有精度缺失
代碼：
[cpp]
#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
using namespace std;
#define MAXN 100000
int t , n;
long long num[MAXN];//保存某一個值的總數
//打表初始化
void init(){
long long i , j , k , tmp;//long long注意
memset(num , 0 , sizeof(num));//初始化
for(i = 1 ; i <= 5 ; i++){//枚舉位數，最大到5位即可
for(j = pow(10,i-1) ; j < pow(10,i) ; j++){
num[j] = num[j-1] ; tmp = (j-pow(10,i-1)+1)*i;
for(k = 1 ; k < i ; k++)
tmp +=(pow(10,k)-pow(10,k-1))*k;
num[j] += tmp;
}
}
}
void solve(){
int i , j , k , pos , ans;
//找到pos位置
for(i = 1 ; i < MAXN ; i++){
if(n > num[i-1] && n <= num[i]){
pos = i ; break;
}
}
//查找
int cnt = n-num[pos-1] ; int sum = 0;
int len , tmp , tmp_j;
for(j = 1 ; j <= pos ; j++){
tmp_j = j;
for(i = tmp_j , len = 0 ; i != 0 ; i/=10) len++;
for(k = len-1; k >= 0 ;k--){
ans = tmp_j/pow(10,k) ; sum++;
if(sum == cnt){
printf("%d\n" , ans);
return;
}
tmp = pow(10,k) ; tmp_j %= tmp;
}
}
}
int main(){
//freopen("input.txt" , "r" , stdin);
init() ; scanf("%d" , &t);
while(t--){
scanf("%d" , &n) ; solve();
}
return 0;
}
