Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
 User ID: Password:
Register

## 类似二分查找

Posted by toacm_3j at 2007-05-13 22:00:17 on Problem 2956
```如果给你一个数，比如25463,我们很容易算出它是第几个不重复数，假设计算这个的函数为f(x),由f(x)的单调性，可用折半查找x0使得f(x0)=给你的数．　　源程序如下：

//  PKU Online Judge
//  2956
//  Repeatless Numbers

#include <iostream>
#include <string>
using namespace std;

unsigned long fac[10];
unsigned long howmany[9];
unsigned long bound[9][2];

void getfac(void)
{
fac[0]=1;
for(unsigned long i=1; i<=9; ++i)
fac[i]=i*fac[i-1];
}

void gethowmany(void)
{
howmany[1]=9;
for(unsigned i=2; i<=8; ++i)
howmany[i]=9*fac[9]/fac[10-i];
for(unsigned j=2; j<=8; ++j)
howmany[j]+=howmany[j-1];
}

void getbound(void)
{
unsigned long p=1;
for(long i=1; i<9; ++i){
bound[i][0]=p;
bound[i][1]=(p*=10)-1;
}
}

string i2s(unsigned long i)
{
string s;
for(; i; i/=10)
s=(char)(i%10+'0')+s;
return s;
}

unsigned long count(string s)
{
int len=s.length();
unsigned 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)
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];
if( repeat )
break;
}
if( repeat )
return t;
else
return t+1;
}

bool repeated(unsigned long n)
{
string s=i2s(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;
}

unsigned long select(unsigned long n,unsigned long a,unsigned long b)
{
unsigned long m=(a+b)/2;
unsigned long temp=count( i2s(m) );
if( temp>n )
return select(n,a,m);
else if( temp<n )
return select(n,m,b);
else{
while( repeated(m) )
--m;
return m;
}
}

long main()
{
getfac();
gethowmany();
getbound();

unsigned long n;
while(cin>>n,n){
if(n<10)
cout<<n<<endl;
else{
int i;
for(i=1; howmany[i]<n; ++i)
;
cout<<select(n-howmany[i-1],bound[i][0],bound[i][1])<<endl;
}
}

return 0;
}```

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator