C语言题目，超时了，该如何处理。。

http://tieba.baidu.com/p/2875513553

3114: {A}∩{B}

时间限制(普通/Java):1500MS/4000MS
运行内存限制:65536KByte
总提交: 1038 测试通过:294

描述

Given two integer sets A and B
sorted descendingly, you are asked to output the element count of A∩B.

输入

Standard input will contain multiple test cases.
The first line of the
input is a single integrate T (1 <= T <= 50) which is the number of test
cases. then T consecutive test cases followed.
In each test case, there has
four lines.
The first line contains the element count N(1<=N<=100000)
for the first set.
The second line contains N integers in the first set.

The third line contains the element count M(1<=M<=100000) for the
second set.
The fourth line contains M integers in the second set.

NOTE: there will be no duplicate elements in each sets and all the integers
in each set have been sorted descendingly.

输出

For each test case in the
input, there's only one line output that contains the element count of the
intesection of the two sets.

样例输入

1
5
5 4 3 2 1
4
5 3 1 -1

样例输出

3

题目来源

台州学院第二届新生程序设计竞赛

题目上传者

crq

http://acm.tzc.edu.cn/acmhome/problemdetail.do?&method=showdetail&id=3114
具体讲一下！！！！！！！！！！！！！！！！！！！！！！！！！！！！！

#include
int main()
{
int T,n,m,i,j,s,k;
int a[100000],b[100000];
scanf("%d",&k);
while(k--)
{ int l=0;
scanf("%d",&m);
for(i=0;i {
scanf("%d",&a[i]);
}
scanf("%d",&n);
for(j=0;j {
scanf("%d",&b[j]);
for(i=0;i {
if(a[i]==b[j])
l++;
}
}

printf("%d\n",l);
}
}

数量比较大，用简单的线性搜索是不行的啦，题目已经说明了输入的集合是降序排好而且没有重复元素的了，对每个b[j]在a数组中可以使用折半搜索。更进一步的，如果能充分领悟到两个集合都是降序的含义，则可使程序跑得更快。
更快的代码：#include 
#include 
int main()
{
    int i, j, k, n, m, s;
    int a[100001], b[100001];
    scanf("%d", &k);
    while(k--)
    {
        scanf("%d", &n);
        for(i=0; i < n; i++)
            scanf("%d", &a[i]);
        a[n] = INT_MIN;
        scanf("%d", &m);
        for(j=0; j < m; j++)
            scanf("%d", &b[j]);
        b[m] = INT_MIN;

        i = j = s = 0;
        while(1)
        {
            while(a[i] > b[j])
                i++;
            while(b[j] > a[i])
                j++;
            if(i == n || j == m)
                break;
            if(a[i] == b[j])
            {
                s++;
                i++;
                j++;
            }
        }
        printf("%d\s", s);
    }
}

本题应采用二分查找。依次从较短的集合中取元素，然后到较长的集合中进行二分查找。时间复杂度将为O(nlogm)，n为较短集合的长度，m为较长的集合的长度。 #include int Search(int *s, int first, int last, int key) { int mid, left = first, right = last; while(left <= right) { mid = (left + right) / 2; if(key == s[mid]) return mid; if(key > s[mid]) right = mid - 1; else left = mid + 1; } return 0; } void main( ) { int a[50][100000], b[50][100000], m[50], n[50], case_count, *set_short, *set_long, len_short, len_long, first, last, index, i, j, count; scanf("%d", &case_count); for(i = 0; i < case_count; i++) { scanf("%d", &m[i]); for(j = 1; j <= m[i]; j++) scanf("%d", &a[i][j]); scanf(%d", &n[i]); for(j = 1; j <= n[i]; j++) scanf(“%d", &b[i][j]); } for(i = 0; i < case_count; i++) { count = 0; if(m[i] < n[i]) { set_short = a[i]; set_long = b[i]; len_short = m[i]; len_long = n[i]; } else { set_short = b[i]; set_long = a[i]; len_short = n[i]; len_long = m[i]; } for(j = 1, first = 1, last = len_long; (j <= len_short) && (first <= last); j++) { index = Search(set_long, first, last, set_short[j]); if(index) { count++; first = index + 1; } else first++; } printf("%d\n", count); } }