今天zyb参加一场面试,面试官听说zyb是ACMer之后立马抛出了一道算法题给zyb:
有一个序列,是1到n的一种排列,排列的顺序是字典序小的在前,那么第k个数字是什么?
例如n=15,k=7, 排列顺序为1, 10, 11, 12, 13, 14, 15, 2, 3, 4, 5, 6, 7, 8, 9;那么第7个数字就是15.
那么,如果你处在zyb的场景下,你能解决这个问题吗
题解
https://blog.csdn.net/FJJ543/article/details/81908992
#include<bits/stdc++.h>
using namespace std ;
#define LL long long
#define INF 0x3f3f3f3f
#define mod 1000000007
int FF(int n , int k)
{
int curr = ;
k = k - ;
while (k > ) {
long steps = , first = curr, last = curr + ;
while (first <= n) {
steps += min((long)n + , last) - first;
first *= ;
last *= ;
}
if (steps <= k) {
curr += ;
k -= steps;
} else {
curr *= ;
k -= ;
}
}
return curr;
} int main()
{ int T;
scanf("%d",&T);
while(T--)
{
int n,k;
scanf("%d%d",&n,&k);
k--;
int cnt=;
while(k)
{
int st= , head=cnt , tail = cnt+;
while(head<=n)
{
st+=min(n+,tail) - head;
head*=;
tail*=;
}
if(st<=k)
{
cnt++;
k-=st;
}
else
{
cnt*=;
k--;
}
}
printf("%d\n",cnt);
}
return ;
}