poj1019 大数据处理 分块

Description

Input

Output

Sample Input

2
8
3

Sample Output

2

粗看想暴力过的，看到20几亿的数据不用想时间肯定超时。昨晚把边界数据大小数了下，本想很繁的题目，今晚真正上机写完估计不用5分钟，当然代码质量可能不是很高，可以更精简些。提交后RE了好几次，就很郁闷了。最后发现一个变量打错，丢死人

记录一下统计结果，当然如果有更好的写法这些数据可能用不上

1~9        共45位

10~99      共9000位               45+9000=9045

100~999    共1386450位            45+9000+1386450=1395495

1000~9999  共188019000位          45+9000+1386450+188019000=189414495

10000~9999 共23750235000位        

第2147483647位于第31268个1...n中

本题用分块方法写的，也许是最笨的写法，有其他更好写法，欢迎指导

#include<iostream>
#include<cmath>
using namespace std;
long a[31270]={0},t,sum=0,i,j,k,len,h,g;
long b[490000]={0};
long f(long n,long x){
	len=0;
	for(g=n;g>=1;g--){
		h=g;
		while(h){
			b[len++]=h%10;
			h/=10;
		}
	}
	return b[len-x];
}
int main(){
	for(i=1;i<10;i++){
		a[i]=a[i-1]+1;
		sum+=a[i];
	}
	for(i=10;i<100;i++){
		a[i]=a[i-1]+2;
		sum+=a[i];
	}
	for(i=100;i<1000;i++){
		a[i]=a[i-1]+3;
		sum+=a[i];
	}
	for(i=1000;i<10000;i++){
		a[i]=a[i-1]+4;
		sum+=a[i];
	}
	for(i=10000;i<100000&&sum<=2147483647;i++){
		a[i]=a[i-1]+5; 
		sum+=a[i];
	}
    cin>>t;
	if(t<1||t>10)return 0;
	while(t--){
		cin>>i;
		if(i<1||i>2147483647)return 0;
		k=i;
		if(i>189414495){
			k-=189414495;
		  for(j=10000;;j++){
		  	if(k>a[j]){
		  	  k-=a[j];continue;
		  	}
		  	else{
		  		cout<<f(j,k)<<endl;
		  		break;
		  	}
		  }	
		}
		else if(i>1395495){
			k-=1395495;
			for(j=1000;;j++){
				if(k>a[j]){
					k-=a[j];continue;
				}
				else{
					cout<<f(j,k)<<endl;
		  		    break;
				}
			}
		}
		else if(i>9045){
			k-=9045;
			for(j=100;;j++){
				if(k>a[j]){
					k-=a[j];continue;
				}
				else{
					cout<<f(j,k)<<endl;
		  		    break;
				}
			}
		}
		else if(i>45){
			k-=45;
			for(j=10;;j++){
			  if(k>a[j]){
					k-=a[j];continue;
			  }
			  else{
					cout<<f(j,k)<<endl;
		  		    break;
			  }	
			}
		}
		else if(i>=1){
			for(j=1;;j++){
			  if(k>a[j]){
					k-=a[j];continue;
			  }
			  else{
					cout<<f(j,k)<<endl;
		  		    break;
			  }		
			}
		}
	}
  return 0;
}