会超时吗?
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 208 Accepted Submission(s): 74
我们可以大致的认为计算机的运行频率约为2*109Hz(当然,如果是多核CPU的话运行速度会更快,这个暂时不考虑)。
可能大家对于计算机的运行速度没有准确的概念,我们在HDOJ上对下面代码进行测试,只需要500MS左右就可以算出结果,当然这个速度比我们平常用的电脑会快一点。
尽管现在的计算机运行速度已经很快了,但是还是无法满足人们不断增长的需求,因此,程序的效率是非常重要的。比如,在ACM比赛中,那些运行效率不符合要求的代码常常会得到TLE的结果。
不过在很多情况下,可以通过算法的时间复杂度和题目的时限以及经验来大致的判断你的代码是否会超时。
可能有些同学不明白什么是算法的时间复杂度,这么说吧,时间复杂度可以用O(n),O(n*n),O(n*n*n), O(log(n)),O(sqrt(n))等等来表示。作为初学者,假设我们只用O(n)和O(n*n)的算法。
对于一个ACM题目,假如他给你的样例总数为T,算法复杂度(假设为O(n)), n的大小,以及限制时间t。那么我们可以用T*n来估计大致的运行次数。如n=106, T=100。那么我们可以大致的认为,程序运行的次数在108这个数量级。
现在,我们粗略的认为:
如果运算量为108或者更少的情况下,这个代码是肯定不会超时的。
如果在108到109之间 ( >108 且 ≤109 )可能会超时,可能不会超时。
如果大于109 ,那么它会超时。
举个例子,如果时间t=2 (s),T=200 ,n=103 ,时间复杂度 O(n*n)。那么运算量为 T*n*n/t=108, 这是安全的。
每一行包含一个字符串 s(长度≤ 10 ),3个整数 n , T , t 。
s,n,T,t 之间都包含一个空格。
字符串s表示算法复杂度,我们保证肯定是O(n*n)或者O(n)。
n , T ,t (1≤ n, T ≤105 , 1≤t≤10 )均表示题目描述中所提到的变量。
n, t , T 均会以数字形式如100000出现,不会以指数形式105或者10^5的形式出现。
int型变量可能不易解决这个问题,推荐用double型或者__int64型。
#include
#include
main()
{
long long int a,b,j,n,m,k,len,i,T,t;
char p[5];
while(scanf("%s",&p)!=EOF)
{
scanf("%I64d %I64d %I64d%*c",&n,&T,&t);
len=strlen(p);
if(len==4)
{
m=(T/t)*n;
}
else if(len==6)
{
m=(T/t)*n*n;
}
if(m