我的解决方案的时间限制超出测试用例。我的解决方案有什么问题？

Codeforces问题119A- http://codeforces.com/problemset/problem/119/A 我的解决方案的时间限制超出测试用例。我的解决方案有什么问题？

我的解决办法：

#include<iostream> 
using namespace std; 
int a,b,i,n; 
int gcd(int x,int y) 
{ 
    int z,c; 
    c=min(x,y); 
    for(i=1;i<=c;i++) 
    { 
     if(((x%i)==0)&&((y%i)==0)) 
     z=i; 
    } 
    return z; 
} 
int main() 
{ 
    cin>>a>>b>>n; 
    while(1) 
    { 

     if(n<gcd(a,n)) 
     { 
      cout<<"1"; 
      break; 
     } 
     else 
     n-=gcd(a,n); 
     if(n<gcd(b,n)) 
     { 
      cout<<"0"; 
      break; 
     } 
     else 
     n-=gcd(b,n); 
    } 
}

我不熟悉的时间constraints.My解决方案是给予正确的结果在常规time.What我的电脑上运行时我应该改变我的解决方案让它在时间限制下运行？我是否应该避免使用用户定义的函数？测试用例为-3,5,9和1,1,100。

来源

2013-12-14 vishal_khanna

“我应该不要使用......功能”否！你应该改进算法，然后再担心你的算法，然后担心你的编译器，然后担心微内优化，比如内联一个微小的纯函数 – jozefg

从某种意义上讲，这比编程问题更像是一个数学问题。如果你研究如何有效地计算'gcd'，那么一个更好的程序会表明它自己。编程不仅仅是为了获得第一个想法而编写代码。这也是研究你正在试图解决的问题，找到解决问题的最佳算法，然后将它们转换成代码。 –

尝试仅计算一次gcd，而不是每个循环两次。 –

您的代码绝对准确并且会得出正确的答案，但可以通过一些小的改进来提高效率并成功通过时间限制。

不要在while循环内计算两次GCD。 GCD是一个昂贵的算法，它运行两次使您的程序的整体完成时间加倍。这可能是您的程序不能生成TLE的最重要的修补程序。
潜在的优化算法GCD，虽然这是没有必要通过所有测试用例（如下图所示）

只使用一次gcd并传递codeforces所有测试用例可能看起来像下面的（提交here的实现）：

#include <iostream> 
using namespace std; 

int gcd(int, int); 

int main() 
{ 
    int a, b, n; 
    cin >> a >> b >> n; 
    while (1) { 
     n -= gcd(a, n); 
     if (n == 0) { 
      cout << "0" << endl; 
      return 0; 
     } 
     n -= gcd(b, n); 
     if (n == 0) { 
      cout << "1" << endl; 
      return 0; 
     } 
    } 
} 

int gcd(int u, int v) 
{ 
    int t; 
    while ((t = u % v) != 0) { 
     u = v; 
     v = t; 
    } 
    return v; 
}

来源

2014-04-22 23:45:09 manan

我的解决方案的时间限制超出测试用例。我的解决方案有什么问题？

回答

相关问题