(DS1.5.10)POJ 1019 Number Sequence(确定一个数字序列中某一个位置上的数字)

/* 
 * POJ_1019.cpp 
 * 
 *  Created on: 2013年10月24日 
 *      Author: Administrator 
 */  
#include <iostream>  
#include <cstdio>  
#include <cmath>  
  
using namespace std;  
  
const int maxn = 31269;  
/** 
 * a[i] :第i个数字序列的长度 
 * s[i] :前i个数字序列的长度 
 */  
long long a[maxn];//在这里如果用int的话会RE,这里要么用long long,要么用unsigned int  
long long s[maxn];  
void prepare(){  
    int i;  
    a[1]=s[1]=1;  
    for(i = 2 ; i < maxn ; ++i){  
        a[i] = a[i-1] + (int)log10((double)i)+1;  
        s[i] = s[i-1] + a[i];  
    }  
  
    return ;  
}  
  
int work(int n){  
    int i = 1;  
    while(s[i] < n){//找到在第几组数字序列  
        ++i;  
    }  
  
    int pos = n - s[i-1];//确定在该组数字序列的哪一个位置  
  
    //确定这个位置在哪一个数上,并找到哪一个数位上的数字  
    int len = 0;  
    for(i = 1 ; len < pos ; ++i){  
        len += (int)log10(double(i)) + 1;  
    }  
    return (i-1)/(int)pow((double)10,len - pos)%10;  
}  
  
int main(){  
    prepare();  
  
    int t;  
    scanf("%d",&t);  
    while(t--){  
        int n;  
        scanf("%d",&n);  
  
        printf("%d\n",work(n));  
    }  
  
    return 0;  
}  

补充：软件开发 , C++ ,

上一个：Leetcode: Clone Graph
下一个：Leetcode: Candy