题解 P7063 【[NWRRC2014]Digits】

· · 题解

前言

首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) 这样子，只优化了三分之二。