POJ 1002 487-3279

学校太让人失望了,居然连POJ都上不去了,还好今天ambition在我用百练AC掉这题后送来了另外一个POJ的网址,双喜临门,害我兴奋了半天,没有POJ的日子痛苦啊。毕竟题目来源还得靠它。

这是曾经没有AC掉的题目,不过在《程序设计导引及在线实践》上看过,看书写代码还是没亲自做的效果好。今天给假期题目来源找题,看中了这题,再次做,强化了一些基本功。

分析几点:

一。A~Z对应一个Hash数组

二。在每输入一个数据时就对数据进行处理,转换字母,去掉’-‘

三。qsort的运行,具体看MSDN,这里就讲一点。

    一个是二位数组的qsort用法:

1
2
3
4
5
6
 int compare( const void *arg1, const void *arg2 )
{
   return strcmp((char*)arg1, (char*)arg2 );
}
int arr[n][11];
qsort(arr, n, sizeof(arr[0]), compare);

  二是qsort的几个参数,这里一直不是记得很清楚。

1
2
3
4
5
6
 void qsort(
   void *base,
   size_t num,
   size_t width,
   int (__cdecl *compare )(const void *, const void *) 
);

  注意:width: Element size in bytes

               cmp函数:如果是升序,则e1 > e2应返回1,e1 = e2 应返回0, e1 < e2 应返回-1.降序则相反。

直接发代码了:

时间有点大,是600多MS。

看见网上还有其他方法,大家可以去看看。

题目地址:

http://124.205.79.250/JudgeOnline/problem?id=1002

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 // POJ 487-3279
// Author: Tanky Woo
#include <iostream>
using namespace std;
 
char hash[] = "22233344455566670778889990";
 
char telphone[100001][20];
char temp[20];
 
int compare( const void *arg1, const void *arg2 )
{
   return strcmp((char*)arg1, (char*)arg2 );
}
 
// www.wutianqi.com
int main()
{
	//freopen("input.txt", "r", stdin);
	int flag = 0;
	int nCases;
	scanf("%d", &nCases);
	for(int i = 0; i < nCases; ++i)
	{
		getchar();
		scanf("%s", telphone[i]);
		int len = strlen(telphone[i]);
		int t = 0;
		for(int j = 0; j < len; ++j)
		{
			if(telphone[i][j] >= 'A' && telphone[i][j] <= 'Z')
				temp[t++] = hash[telphone[i][j]-'A'];
			else if(telphone[i][j] >= '0' && telphone[i][j] <= '9')
				temp[t++] = telphone[i][j];
			else if(telphone[i][j] == '-')
				;
		}
		strcpy(telphone[i], temp);
	}
 
	qsort(telphone, nCases, sizeof(telphone[0]), compare);
 
 
	for(int i = 0; i < nCases; ++i)
	{
 
		int cnt = 1;
		strcpy(temp, telphone[i]);
		int j;
		for(j = i+1; j < nCases; ++j)
		{
			if(strcmp(temp, telphone[j]) == 0)
				cnt++;
			else
				break;
		}
		if(cnt > 1)   //这个地方没处理好,麻烦。。。
		{
			flag = 1;
			for(int k = 0; k < 3; ++k)
				printf("%c", temp[k]);
			printf("-");
			for(int k = 3; k < 7; ++k)
				printf("%c", temp[k]);
			printf(" %d\n", cnt);
		}
		i = j-1;
	}
	if(flag == 0)
		printf("No duplicates.\n");
 
 
	return 0;
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《POJ 1002 487-3279》有1个想法

  1. 600多MS呀……我看到这道题上有人居然双位数毫秒就解决了,不知道是因为那是测试数据少还是真的程序就那么牛。我一开始用数组记录然后最后来个快排,使用740K的内存和563MS的时间;于是想着用哈希可能速度能够快不少,结果速度没减多少(532MS),内存消耗却多达3212K……

发表评论

电子邮件地址不会被公开。 必填项已用*标注