AcWing 4653. 数位排序
原题链接
简单
作者:
zxcpyy
,
2023-01-03 21:21:32
,
所有人可见
,
阅读 132
用邻接表存储和是头下标的所有数,从1开始枚举每个单链表,用res存储累加和,直到res >= m 停下,因为是头插法,所以要找出最后一次单链表,从表尾到表头的 第 m - b 个数 ,这就是第m 个数,b 是上一次循环结束后的 res ;
#include<iostream>
#include<cstring>
using namespace std;
const int N = 1000010;
int h[60],ne[N],e[N],idx;
void add(int x,int y)
{
e[idx] = y, ne[idx] = h[x], h[x] = idx ++;
}
int main()
{
memset(h,-1,sizeof h);
int n,m;
cin >> n >> m;
for(int i = 1 ;i <= n;i ++)
{
int sum = 0;
int t = i;
while(t )
{
sum += t % 10;
t /=10;
}
add(sum , i);
}
int res = 0;
int b = 0;
int ans = 0;
int u = 0;
for(int i = 1;i <= 54 ;i ++)
{
b = res ;
for(int j = h[i]; j != -1; j = ne[j])
res += 1;
if(res >= m)
{
u = res - b;
int r = m - b;
int t = 0;
for(int j = h[i];j != -1 ;j = ne[j])
{
t ++ ;
if(t == u - r + 1)
{
ans = e[j];
break;
}
}
}
}
cout << ans << endl;
return 0;
}