c++ - 如何使我的代码与众不同以消除时间限制？

Question

问题是：有一条8位数字的票。第一张票的编号为 M ，最后一张为 N 。量级 M 和 N 满足以下关系：10000000 ≤ M < N ≤ 99999999。您需要确定给定数字之间的“幸运”票数。如果前四位数字的总和等于后四位数字的总和，则彩票被视为“幸运”。这是我的代码：

#include <iostream>
#include <fstream>
#include <iomanip>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
int calcSumDigits(int n)
{
    int sum=0;
    while (n!=0)
    {
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int main(void)
{
    int a,b,cnt=0,x,y;
    cin>>a>>b;
    for (int i=a;i<=b;i++)
    {
        x=i%10000;
        y=(i-x)/10000;
        if (calcSumDigits(x)==calcSumDigits(y)) cnt++;
    }
    cout<<cnt;
    return 0;
}

结果是正确的，但是程序需要很长时间才能给出结果。例如，当我尝试从 10000000 到 99999999 时，结果显示 4379055 但需要超过 6 秒

Answer 1

您只需要比较由每半个数字的所有排列生成的两组总和 - 为简化起见，我将数字四舍五入：

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
int calcSumDigits(int n)
{
    int sum=0;
    while (n!=0)
    {
        sum+=n%10;
        n/=10;
    }
    return sum;
}
int SlowVersion(int a, int b) {
    int cnt=0,x,y;
    for (int i=a;i<=b;i++)
    {
        x=i%10000;
        y=(i-x)/10000;
        if (calcSumDigits(x)==calcSumDigits(y)) cnt++;
    }
    return cnt;
}
int main()
{
    int lower;
    int upper;
    int original_lower;
    int original_upper;
    cout<<"enter lower:";
    cin>>original_lower;
    cout<<"enter upper:";
    cin>>original_upper;

    lower = original_lower - (original_lower%10000);
    upper = original_upper + (9999 - (original_upper%10000));

    cout<<"to simplify the calculations the lower was changed to:" << lower << endl;
    cout<<"to simplify the calculations the upper was changed to:" << upper << endl;

    int cnt=0;
    const int b=lower%10000;
    const int a=(lower-b)/10000;
    const int b_top=upper%10000;
    const int a_top=(upper-b_top)/10000;
    int a_sums[a_top-a];
    int b_sums[b_top-b];


    int counter = 0;
    for (int i=a;i<=a_top;i++)
    {
        a_sums[counter] = calcSumDigits(i);
        counter++;
    }
    counter = 0;
    for (int x=b;x<=b_top;x++)
    {
        b_sums[counter] = calcSumDigits(x);
        counter++;
    }

    int countera = 0;
    int counterb = 0;
    for (int i=a;i<=a_top;i++)
    {
        counterb = 0;
        for (int x=b;x<=b_top;x++)
        {
            if (a_sums[countera]==b_sums[counterb]) cnt++;
            counterb++;
        }
        countera++;
    }

    cnt = cnt - SlowVersion(lower,original_lower-1);
    cnt = cnt - SlowVersion(original_upper+1,upper);

    cout << "The total \"lucky numbers\" are " << cnt << endl;

    cout << "a is " << a << endl;
    cout << "b is " << b << endl;
    cout << "a_top is " << a_top << endl;
    cout << "b_top is " << b_top << endl;
    system("PAUSE");
    return 0;
}

输入结果为 4379055（与您得到的结果相同）并且运行速度非常快。