注册 登录
编程论坛 数据结构与算法

求解一个ACM基础题

li362490567 发布于 2015-10-01 18:29, 2201 次点击
求解一个ACM基础题
因为我暂时没学算法,导致做这个题目时,程序超时,以下是题目:
Description:
We know that if a phone number A is another phone number B’s prefix, B is not able to be called. For an example, A is 123 while B is 12345, after pressing 123, we call A, and not able to call B.
Given N phone numbers, your task is to find whether there exits two numbers A and B that A is B’s prefix.

Input:
The input consists of several test cases.
The first line of input in each test case contains one integer N (0<N<1001), represent the number of phone numbers.
The next line contains N integers, describing the phone numbers.
The last case is followed by a line containing one zero.

Output:
For each test case, if there exits a phone number that cannot be called, print “NO”, otherwise print “YES” instead.

Sample Input:
2
012
012345
2
12
012345
0

Sample Output:
NO
YES
3 回复
#2
li3624905672015-10-01 18:30
这是我原版代码:
#include<stdio.h>
#include<string.h>
int main(void)
{
    int  a,i, j, k, h = 0;
    first:while (scanf("%d", &a),a!=0)
    {
        
        char pnumber[a][20];
        for (i = 0; i < a; i++)
            gets(pnumber[i]);
        for (i = 0; i < a-1; i++)
            for (j = i + 1; j < a; j++)
            {
                k = 0;
                while (pnumber[i][k] == pnumber[j][k] && h < strlen(pnumber[i]))
                {
                    k++;
                    h++;
                }
                if (h == strlen(pnumber[i]))
                {
                    printf("NO");
                    goto first;
                }
            }
        printf("YES");
    }
    return 0;
}
但是算法很烂,时间太久
#3
li3624905672015-10-01 18:30
求解
#4
li3624905672015-10-01 21:35
求解啊啊啊啊
1