各数位不重复的数.txt

ACM资料大集合

#include <iostream>
#include <string>
#include <stdio.h>
using namespace std;

long fac[10];
long howmany[9];

/*
题目：各数位不重复的数
输入：
10000

输出：
26057
*/
//思路：通过二分法查找，找到所要的数
void getfac()
{	//计算阶乘
	int i;
	fac[0]=1;
	for(i=1; i<=9; ++i)
		fac[i]=i*fac[i-1];
}

void gethowmany()
{	//求某位数符合条件的个数
	int i,j;
	howmany[1]=9;
	for(i=2; i<=8; ++i)
		howmany[i]=9*fac[9]/fac[10-i];
	for(j=2; j<=8; ++j)
		howmany[j]+=howmany[j-1];
}

void getlimit(long *min,long *max)
{	//求某位数的最小值和最大值
	int i;
	long p=1;
	for(i=1; i<9; ++i){
		min[i]=p;
		p=p*10;
		max[i]=p-1;
	}
}

string getstr(long i)
{	//将数字转化为字符串
	string s;
	for(; i; i/=10)
		s=(char)(i%10+'0')+s;
	return s;
}

long count(string s)
{	//计算该数在数组中的位置
	int len=s.length();
	long t=(s[0]-'0'-1)*fac[9]/fac[10-len];//最高位占数组的大小
	bool repeat=false;
	for(int i=1; i<len; ++i)
	{
		int less=0;
		for(int j=0; j<i; ++j)
		{
			//前面已经有比第i位小的数字了，第i位从0增加到当前数字时要跳过这些数字
			if(s[j]<s[i])
				++less;
			else if(s[j]==s[i])
				repeat=true;
		}
		t+=(s[i]-'0'-less)*fac[9-i]/fac[10-len];//后面的第i位所占数组的大小
		if( repeat )
			break;
	}
	if( repeat )
		return t;
	else
		return t+1;
}

bool repeated(long n)
{	//判断是否符合条件
	string s=getstr(n);
	int flag[10];
	memset(flag,0,sizeof(flag));
	for(int i=0; i<s.length(); ++i)
		++flag[s[i]-'0'];
	for(int j=0; j<10; ++j)
		if(flag[j]>1)
			return true;
	return false;
}

long find(long n,long a,long b)
{
	long m=(a+b)/2;
	long temp=count(getstr(m));
	if( temp>n )//所求的数更小
		return find(n,a,m);
	else if( temp<n )//所求的数更大
		return find(n,m,b);
	else{
		while( repeated(m) )  
			m--;//调整
		return m;
	}
}

int main()
{
	long n,i;
	long min[9],max[9];

	getfac();
	gethowmany();
	getlimit(min,max);
	cin>>n;
	while(n!=0)
	{
		if(n<10)
			cout<<n<<endl;
		else
		{
			for(i=1; howmany[i]<n; i++);
			cout<<find(n-howmany[i-1],min[i],max[i])<<endl;
		}
		cin>>n;
	}
	return 0;
}