UVA - 10706 Number Sequence 子序列

#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;

const int maxn = 32761;
long long S[maxn];//存放的是S1，S2，到SK的和，S[5]表示了S1到S4的和,当数字变化到K的时候，一共有多少个字数了
int border[9] = {0,1,10,100,1000,10000,100000,1000000,10000000};
int num[9] = {0,9,90,900,9000,90000,900000,9000000,90000000};//num[1]存放1-9的位数，num[2]存放1-99的位数，以此类推，刚开始初始话成这样，是为了后面的计算

int getdigit(int n) {
	int count = 0;
	while(n > 0) {
		count++;	
		n = n / 10;
	}
	return count;
}

void init() {
	for(int i = 2; i < 9; i++)//位数的变化，num[2]存放的是1-99的位数，因为十位数要占两位，所以要用90个十位数＊2，再加上前面的9个个位数，就是1-99的位数了，以此类推，num里面的下标表示的位数
		num[i] = num[i-1] + num[i] * i;
	S[0] = 0;
	int digit;
	for(int i = 1; i < maxn; i++) {
		digit = getdigit(i);
		S[i] = (i - border[digit] + 1 )	* digit + num[digit-1];
		S[i] =  S[i] + S[i-1];
	}
}

int main() {
	int n;
	int N;
	scanf("%d",&n);
	init();
	while(n--) {
		scanf("%d",&N);
		long long *p = lower_bound(S,S+maxn,N);
		if(*p == N) 
			printf("%d\n",(p-S) % 10);
		else {
			int len = N - *(p-1);
			bool flag = false;
			int i;
			for(i = 0; i < 9; i++) {
				if(num[i] == len) {
					flag = true;
					break;	
				}
				else if(num[i] > len)
					break;	
			}

			if(flag){
				printf("9\n");
				continue;
			}
			int last = len - num[i-1];
			int k;
			int count = i;
			for(k = border[i]; count < last; count += i,k++);;

				int time = count - last;
			while(time > 0) {
				k = k / 10;
				time--;
			}
			printf("%d\n",k % 10);
		}
	}
	return 0;
}