自动搬运

查看原文

来自洛谷，原作者为

	Error_Eric 终究还是意难平

搬运于2025-08-24 22:26:18，当前版本为作者最后更新于2020-12-12 09:56:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

首A!

正文

这是一种暴力的解法，如果大家有更好的解法欢迎提出。

思路：枚举 1~很大 之间的所有正整数，统计每一个数位和出现的次数，用 sum 数组维护每一个数位和的数字的和，然后用 ans 变量维护答案。

我的第一版代码是这样的：

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int f(int x){//计算数位和，复杂度 lg x .
	int tot=0;
	while(x)tot+=x%10,x/=10;
	return tot;
}
int n,u,di=0,cnt[500];//cnt维护每一个数位和的数字出现的次数.
long long sum[500]={-0x7fffffff,0};
long long ans=0x7fffffffffffffll;//题目中已说明
int main(){
	scanf("%d",&n);//输入
	for(int i=1;i<=600000;i++){//枚举正整数
		u=f(i),(cnt[u]<n)?(cnt[u]++,sum[u]+=i):0;//维护
		if(cnt[u]==n)ans=min(ans,sum[u]);//如果cnt恰好是 n , 维护 ans
	}
	printf("%d\n",ans);//输出答案 .
} 

时间复杂度 $\Theta(\sum_{i=1}^{600000}\lceil\lg x\rceil)$

大概是 $\Theta(3488889)$ 这个样子，是一个很大的常数 。

这个时候，脑海中有一个声音出现了：“我不满意！”

即使是常数复杂度，也可以优化！

优化1

把目光投向 f(x) 。

可以发现，经常有不必要的计算，比如前一次计算了 12345654321234321 后一次就要计算 12345654321234322 （当然没有这么大的，只是举个例子），很浪费时间！

不过，我们可以发现，只有这个数字末尾的数字是 $9$ 时，这个函数再算一遍才有意义。不然就是上一次的答案加 $1$ 。

我们可以得到以下优化：

int las,lan;
int f(int x){
	if(las%10!=9)return (las=x),++lan;
	int tot=0;
	while(x)tot+=x%10,x/=10;
	return tot;
}

函数复杂度缩减为90%情况 $\Theta(1)$ .

优化2

把目光投向 for(int i=1;i<=600000;i++) 。

可以发现 $600000$ 是个过大的数。

稍微输出一下最大的数字，可以发现，$n=5000$ 时， $i$ 最大有效不过 $586775$ 而已。

可以得到以下优化：

for(int i=1;i<=586775;i++)

优化3

把目光投向 long long ans 。

经测验，不开 long long 是可以的，答案最大是$193969046$ 。

优化4

经测验，数位和最大 $50$ 而已。

cnt,sum开 $51$ 足矣。

最终得出代码：

Code

#include<iostream>
#include<algorithm>
#include<stdio.h>
using namespace std;
int n,u,cnt[51],las,lan;
int sum[51],ans=193969046;
int f(int x){
	if(las%10!=9)return (las=x),++lan;
	int tot=0;
	while(x)tot+=x%10,x/=10;
	return tot;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=586775;i++)
		u=f(i),cnt[u]++,sum[u]+=i,(cnt[u]==n)?(ans=min(ans,sum[u])):0;
	printf("%d\n",ans);
} 

时间复杂度是 $\Theta[\sum_{i=1}^{586775}(i\mod10=9?\lg x:1)]$

大概是 $\Theta(1137639)$ 这样子，只优化了三分之二。