AcWing 4653. 数位排序(常数较小的sort,算法复杂度nlogn)
原题链接
简单
作者:
@陈先生
,
2023-01-04 01:25:43
,
所有人可见
,
阅读 166
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m;
pair<int,int> h[1000010];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int sum1=0,x=i;
while(x)
{
sum1+=x%10;
x/=10;
}
h[i]={sum1,i};
}
sort(h+1,h+n+1);
cout<<h[m].second;
return 0;
}
一开始想的是重载一下sort的比较函数,但重载后发现当n=999999时会超时qwq,然后看了y总的分享和大佬的题解
才知道,当n<=10的6次方的时候用sort的话只能用常数较小的sort才能过。鸣谢大佬的题解和y总的分享,顺便粘一下
重载比较函数的写法,留个纪念,毕竟是第一次重载sort的比较函数。
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
bool cmp(int a,int b)
{
int suma=0,sumb=0,tempa=a,tempb=b;
while(tempa||tempb)
{
suma+=tempa%10;
sumb+=tempb%10;
tempa/=10;
tempb/=10;
}
if(suma!=sumb) return suma<sumb;
else return a<b;
}
int main()
{
int n,h[1000010]={},m;
cin>>n>>m;
for(int i=1;i<=n;i++) h[i]=i;
sort(h,h+n+1,cmp);
for(int i=1;i<=n;i++)
cout<<h[i]<<" ";
cout<<endl;
cout<<h[m];
return 0;
}