时间戳

首页 > 解决方案 > 由于在 C++ 范围内查找完美正方形时出现超时错误而终止

c++ - 由于在 C++ 范围内查找完美正方形时出现超时错误而终止

问题描述

我正在尝试解决 Hackerrank （链接）中的 Sherlock 和 Square 问题，以便在一系列数据中找到完美的正方形。通过了 4 个测试用例，但我收到大量的超时错误。请提出一些改进其性能的建议

我的代码如下：

#include<iostream>
#include<cmath>

using namespace std;

int squares(int a, int b) {
    long double i;
    long long int count=0;
    for(i=a;i<=b;i++)
    {
        long double b = sqrt(i);
        if(fmod(b,1)==0.000000)
        {
            count++;
        }
    }
    return count;
}

int main()
{
    int q,i,a,b;
    cin>>q;
    for(i=0;i<q;i++)
    {
        cin>>a>>b;
        int result = squares(a, b);
        cout<<result<<"\n";
    }
}

标签： c++c++11

解决方案

对于大输入，例如运行超过 16 秒，您的速度问题是显而易见的

1
1 1000000000

因此，简单的解决方案是摆脱 中的循环squares()，并对其进行解析计算：

int squares(int a, int b) 
{
    auto sqrt_from = a < 0 ? 0 : static_cast<int>(std::ceil(std::sqrt(a)));
    auto sqrt_to = b < 0 ? 0 : static_cast<int>(std::floor(std::sqrt(b)));
    return std::max(sqrt_to - sqrt_from + 1, 0);
}

当然，如果您在输入端阻止负值，那么一切都可以完成unsigned，您将获得另一点：

unsigned squares(unsigned a, unsigned b) 
{
    auto sqrt_from = static_cast<unsigned >(std::ceil(std::sqrt(a)));
    auto sqrt_to =   static_cast<unsigned >(std::floor(std::sqrt(b)));
    return std::max(sqrt_to - sqrt_from + 1, 0);
}

推荐阅读