算法1
简单模拟,a[i].x
记录原数,a[i].y
记录各位之和,cmp
排序一下即可
参考文献
C++ 代码
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
struct node{
int x,y;
}a[N];
bool cmp(node a,node b)
{
if(a.y!=b.y)return a.y<b.y;
return a.x<b.x;
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
a[i].x=i;
int t=i;
while(t){
a[i].y+=t%10;
t/=10;
}
}
sort(a+1,a+1+n,cmp);
cout<<a[m].x;
}
没想到先存数位和,比较的时候才算,然后就超时了,5555
aaa为什么呢大佬qaq
我也是,哈哈哈哈
先预处理时间复杂度O(nlogn)。不先预处理排序花费的时间复杂度为O(nlogn)里面嵌套求n个数的数位和O(n),总时间复杂度为O(n*nlogn)
为什么要定义一个新的变量int t,如果我不定义的话,直接写while就会卡输入
不定义不会编译错吗。。
额,我用的devcc++,没有报错提示,就是我直接写while(i)
{
a[i].y+=i%10;
i/=10;
}这样子写的
因为for循环用的是i,如果while还用程序就错乱了
i一直都是0
谢了
y总讲课的时候说map会超时,为什么我写的还是a了呢?请问要是用map存数位之和的话,时间复杂度怎么算的(主要是map的时间复杂度怎么算)?
大佬,想问一下我这个代码为什么会超时啊
#include [HTML_REMOVED]
using namespace std;
int a[1000010];
int swh(int y){
int yy=y;
int sum=0;
while(yy){
sum+=yy%10;
yy/=10;
}
return sum;
}
bool cmp(int a,int b){
int aa=swh(a);
int bb=swh(b);
if(aa!=bb){
return aa[HTML_REMOVED]>n;
cin>>m;
for(int i=0;i<n;i++) a[i]=i+1;
sort(a,a+n,cmp);
cout<<a[m-1];
return 0;
}
每个数的数位和,要先预处理出来
厉害
tql
谢谢
突然恍然大悟,如果在
sort
里面用lambda
函数进行计算,那么每次比较都要对数字进行一次比较。但是如果提前算好了,就避免了在sort里面进行无意义的计算了。
确实是我太菜了,没想到这一点,还以为是
sort
函数的问题,以为只有nth_element
才能过。感谢分享,太牛逼了
### 感谢分享
为什么最后的排序要写成w+1啊
?哪里
如果我把cmp改成
bool cmp(node a,node b)
{
if(a.y < b.y)return true;
return a.x<b.x;
}
就会直接超时,为啥呢?
太腻害了, %%%
大佬牛逼
不用sort 用自己写的冒泡会超时为什么。。
orz
用堆比直接排序还慢
兄弟们这个方法哪里错了?求解(我是ikun)
#include[HTML_REMOVED]
using namespace std;
int ikun(int m)
{
int sum = 0;
int a;
a = m % 10;
while (m!=0)
{
m /= 10;
sum += m;
}
return (sum+a);
}
int main()
{
int a[1000] = { 0 };
int sum[1000] = {0};
int m;
cin >> m;
int n;
cin >> n;
for (int i =1; i <=m ; i)
{
sum[i] = ikun(i);
}
for (int i = 1; i < m; i)
{
for (int j = 1; j < m - i; j++)
{
if (sum[i] > sum[i + 1])
{
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
cout << a[n];
}
###想问问大佬为啥这样子错了嘞,感觉函数有问题但是不太懂
把各位之和放到外面算,放里面执行多次会超时
我这个感觉还没到考虑超时的问题,因为我单纯用样例13 5是没有错误,排序是正确的,但是报错:50 29 这组时,排序顺序就错了,我感觉我的问题应该是各位之和要把它先整体求出来比较,我这样一步一步算就会很局部考虑问题。。。但是我不明白为什么
哥你排序思路是错的……
如果数位和相等,你应该比较a<b,这个没问题,但剩下的情况直接return asum<bsum不就行了吗……
你应该是sort的cmp函数没太学明白
已经不是局部的问题了,sort cmp函数就是返回假不交换两个数,返回真交换,哪有你这样一会a[HTML_REMOVED]b的……这样写的确实有但这道题就是大错特错
嘿嘿,我也觉得是这个问题,谢谢
好嘞,明白咯