Question

ACM总是Time Limit Exceeded，到底是WRONG ANSWER还是算法太暴力，还是死循环或是什么别的问题呢？

我的C++代码：
#include<iostream>
using namespace std;
int main()
{
int n,i,j,q,a[100000],k;
while(cin>>n)
{
for(i=1;i<=n;i++)
{
cin>>a[i];
}
cin>>q;
for(j=1;j<=q;j++)
{
cin>>k;
for(i=1;i<=n;i++)
{
if(k==a[i])
{
cout<<i<<endl;
goto A;
}
else if(i<n) continue;
else cout<<"-1"<<endl;
A:
break;
}
}
}
return 0;
}

我改后的代码：
#include <stdio.h>
int main()
{int n,i,j,q,a[100000],k;
while(scanf("%d",&n))
{for(i=1;i<=n;i++)
{scanf("%d",&a[i]);
}
scanf("%d",&q);
for(j=1;j<=q;j++)
{scanf("%d",&k);
for(i=1;i<=n;i++)
{if(k==a[i])
{printf("%d",i);
printf("\n");
break;
}
else if(i<n) continue;
else printf("-1\n");
break;
}
}
}
return 0;
}

无论是哪一种都是Time Limit Exceeded，是哪里出错了，或是可以怎样优化，请求帮忙，小女子感激不尽！





Answer 1

你的代码是没有错的 只是某个tesecase执行时间超过的限制 你想想假如我n=50000 q=100000 你的程序最好的情况要查找多少次？ 100000 * （1 + 2 + 3 + 。。。 50000）

你要取巧已空间换时间 定义一个 100001 的数组a ， i（1-n） 每输入一个数 k a[k] = i 那么下面每次查找一个数只要一次 即将输入要查找的数单做a的下标

Answer 2

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdio.h>
#include <math.h>
using namespace std;
int num[100010];
int main(void)
{
	int n,q,i,idx;
	while(scanf("%d",&n)!=EOF){
		memset(num,0,sizeof(num));
		for(i=1;i<=n;i++){
			scanf("%d",&idx);
			num[idx]=i;
		}
		scanf("%d",&q);
		while(q--){
			scanf("%d",&idx);
			if(num[idx]==0)
				printf("-1\n");
			else
				printf("%d\n",num[idx]);
		}
	}
	return 0;
}

请参考这段代码哈，欢迎交流。满意请采纳。

Answer 3

额外开一个数组就能搞定了。 你的复杂度是n*q的，实际上只要O(n)就可以了。

追问

技术小白，请问要怎么弄？希望能够详细解答！

追答

有人已经贴出代码了，应该很好理解，好好看吧。