一道c++ ACM的题目

Question

http://acm.tju.edu.cn/toj/vcontest/showp9135_F.html这个是题目网址，代码超时了怎么解决。。。我是完完全全的新手，所以请尽量简单的解释一下 谢谢了

#include <iostream>
using namespace std;
int main()
{
int M[4000],N[160000];
int m,n,a=0;
cin>>m>>n;
for(int i=0;i<m;i++)
{
cin>>M[i];
}
for(int i=0;i<n;i++)
{
cin>>N[i];
}

for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)
{
if(M[i]==N[j]){a+=1;}
}
}
cout<<a<<endl;
return 0;
}

Answer 1

因为数据可达到2^31,至少使用unsigned long 存储数据
你的算法是O(NM)的
M=4000,N=160000,N*M=640000000,超过1亿,一般一定会超时。
此题有一个较好的算法是先对第二个数组排序,然后第一个数组的每个元素,二分查找他是否在第二个数组出现,复杂度O((M+N)lgN),肯定不会超时。
#include<algorithm>
using namespace std;
sort(N,n+N);
a=0;
for(int i=0;m>i;++i) a+=binary_search(N,n+N,M[i]);
cout<<a<<'\n';

至于输入输出时间,不是主要问题。
另外,本题有可能是多组输入输出
所以推荐将所有代码用while(cin>>m>>n){}括起来

sorry,如果排序和二分查找第一个数组,复杂度O((M+N)lgM),效果应该更好追问

排序时不会用时吗

追答

用std::sort();是改进版快排,时间复杂度O(NlgN),已经很快了,不会超过时间限制的。你的粗暴算法O(N*M)才会超时。

Answer 2

首先你要先试试修改输入输出，C语言的printf 和 scanf 比c++的cin cout效率要高很多，尤其是有很多输入的时候！先试一下吧，别忘了头文件<cstdio>
然后如果还超时的话再看看算法或数据结构有什么可以改进的吧！
另外你那代码有点问题哦，因为他说每个数都在(0~2^31).之间，你用int显然放不下，用什么都放不下的。我觉得这道题不是很适合新手哦……

Answer 3

代码超时就是算法太慢了呗
你现在算法太粗暴了，O(N^2)了都

我也不是acm的大拿，你试试排序以后再处理, 可以改善成O(N logN)
说错了请不要喷

Answer 4

用位图来运算 另外不要用cin cout