洛谷题目CF96B Lucky Numbers的分析

科技前沿 • 2025-02-07 18:12 • 阅读 48

大家好，我是讯享网，很高兴认识大家。

题目描述：
佩佳喜欢幸运数字。每个人都知道，如果正整数的小数表示不包含除4和7以外的数字，那么它们是幸运的。例如，数字47,744，4是幸运的，5，17,467不是。如果幸运数的十进制表示包含相同数量的数字4和7，则幸运数是超级幸运的。例如，数字47,7744，是超级幸运，4，744,467不是。有一天，Petya遇到了一个正整数n。帮助他找到最少的超级幸运数，它不少于n。
输入格式：
唯一的一行包含一个正整数n(1<=n<=10^{9}1<=n<=10 9)。这个数字没有前导零。
输出格式：
输出大于或等于n的最小超级幸运数。请不要使用%lld指定符在C++中读取或写入64位整数.最好使用cin、cout流或%I64d指定符。
思路分析及求解过程说明：
本题使用C++完成。刚拿到这道题的时候，想法就是从n开始判断每一个数的各个数位是不是均由4或7组成，如果是则进一步判断4和7的数量是否一样，在遇到第一个符合条件的数字后停止执行程序。本质是一种枚举，但是在n很大的时候要判断的数比较多，所以可能会超时，然后大致写了一下这种方法的代码，测试样例在本地也确实都过了，但是在提交到洛谷上的时候TLE了，如下图所示：
在这里插入图片描述
讯享网
然后就要更换思路，首先通过超级幸运数字的特点可以知道输出的数字的数位一定是偶数位，而在前一种方法中会遍历不小于n的奇数位和偶数位数字，故当判断奇数位数字的时候便会大大浪费时间。然后我大概计算了一下所有可能输出的数字的个数，因为n<=10^9，故输出的最大数字为，再计算八位数以内的数字，共有2+6+20+70=98个，（对于有2n位的数字，由于其有n位为4，另外n位为7，通过运用高中数学知识可知其共有（2n）！/（n！）²种可能情况）所以一共有99个可能输出的数字，所以可以开一个数组，直接把它们按从小到大顺序储存在数组中，然后直接从小到大依次与n比较，直到遇上第一个不小于n的数字为止。最后使用这种方法在洛谷AC了这道题，所用时间为1.30秒，然后我大概翻了八页的提交记录，最快的用时为1.11秒（看来枚举还挺好用的哈）。然后发现题解里面也有用这种方法的，不过那个人把十位数的所有情况也算在内了，所以数组开到了350（所有符合条件的十位数有252个），耗时比我长一点。
在这里插入图片描述
源代码

#include<iostream> using namespace std; long long x[99]={ 
   47,74,4477,4747,4774,7447,7474,7744,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,}; int main() { 
    int n; cin>>n; for(int i=0;i<350;i++){ 
    if(x[i]>=n){ 
    cout<<x[i]<<endl; return 0; } } return 0; }

讯享网

洛谷题目CF96B Lucky Numbers的分析

相关推荐