题目意思: 有一个数组 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不然会有精度缺失
代码:
#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; }