1
2
3
4
5
6
7
8
9
10
11
12
|
题目：
给出n个仅由小写字幕构成的字符串，仅按其首字母排序。（若首字母相同，则直接维持原来的顺序。）
输入格式：
第一行为n。
接下来n行，每行一个串。
输出格式：
n行，按排好的顺序，每行一个串。
数据规定：
n <= 1000, 串长小于100000。
|
话说这题前前后后每周大概抽两个小时来搞这题，未怀疑过评测系统出问题，因为我看见老师过了。
前前后后拖了一个月的时间。
放上最终的代码：
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
|
#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <string>
#include <algorithm>
#include <vector>
#include <map>
#include <time.h>
using namespace std;
struct Value
{
char str[10000];
};
void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;
//开辟临时存放字符串的空间
char *p = (char *)malloc( sizeof(char)*10000*n );
//保存地址
for( i = 0; i < n; i++ )
temp[i] = &a[i].str[0];
//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( p + i*10000 ,temp[i] );
//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, p + i*10000 );
free(p);
}
int n;
Value a[5000];
int main()
{
scanf("%d", &n);
for (int i = 0; i<n; i++)
{
scanf("%s", a[i].str);
}
structSort(a, n);
for (int i = 0; i<n; i++)
{
printf("%s\n", a[i].str);
}
printf("\n\nTime used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));
return 0;
}
|
下面详细说说这道题碰见的事情。
1、排序算法的选取
一开始并没有太在意这道题有什么特别之处，感觉特别平常的一道题，想想冒泡太慢，快排不熟悉，于是选择了相对简单的选择排序。
提交了好几次发现问题，选择排序并不能保证：“若首字母相同，则直接维持原来的顺序。” （排序的稳定性）
下面是反例：
数据为：
wjbzbmr
wa
ac
orz
tle
如果是选择排序最后的结果会变成：
ac
orz
tle
wa
wjbzbmr
于是果断滚回去用了冒泡，结果直接用冒泡会超时，这是字符串复制照成的(代码如下)。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void structSort(Value *a, int n)
{
int i = 0, j = n;
Value help;
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( a[i].str[0] >a[i+1].str[0] )
{
help = a[i];
a[i] = a[i+1];
a[i+1] = help;
}
}
|
刚开始没有思考是什么原因造成的，马上开始着手使用快排。
猛然想到，快排和选择排序一样，会造成上面反例的结果。所以当时瞬间傻了一阵子。
后来想到，即使冒泡没有花多少时间，但是主要时间则花在了交换两个字符串上。
所以，开始采用地址的做法。
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
|
void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;
char temp_str[1000][100000];
//保存地址
for( i = 0; i < n; i++ )
temp[i] = &a[i].str[0];
//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( temp_str[i], temp[i] );
//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, temp_str[i] );
free(p);
}
|
上面的做法直接在函数内申请了char temp_str[1000][100000];直接导致栈溢出。
所以后来改成了动态内存分配的方法。
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
|
void structSort(Value *a, int n)
{
int i = 0, j = n;
char *temp[1000];
char *help;
//开辟临时存放字符串的空间
char *p = (char *)malloc( sizeof(char)*10000*n );
//保存地址
for( i = 0; i < n; i++ )
temp[i] = &a[i].str[0];
//冒泡排序
for( j = n; j > 0; j-- )
for( i = 0; i < j-1; i++ )
if( *temp[i] > *temp[i+1] ) // 对地址进行排序
{
help = temp[i];
temp[i] = temp[i+1];
temp[i+1] = help;
}
//按地址从结构体拷出
for( i = 0; i < n; i++ )
strcpy( p + i*10000 ,temp[i] );
//拷贝回结构体
for( i = 0; i < n; i++ )
strcpy(a[i].str, p + i*10000 );
free(p);
}
|
得到了最终的代码。
2、数据构造
但是这TNND死活就不过，十个测试数据，对两个，其他八个属于运行错误。
然后被这个错误折腾了半个月，今天终于知道了，原来我代码是正确的，错在评测系统。
构造了一个极限数据：1000*10000的数据包。
使用下面的程序来造数据：
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
|
#include <stdio.h>
#include <windows.h>
#include<stdlib.h>
#include<time.h>
#define R 1 //随机数启用1
int main()
{
FILE *fp;
char desktop[100];
char str1[20]={0};
unsigned long size=20;
GetUserName(str1,&size);
sprintf(desktop,"C:\\Users\\%s\\Desktop\\%s",str1,"1.in");
freopen(desktop,"w",stdout);
#if(R==1)
int number;
int N=123 ; //0到？内的随机数
srand(time(NULL)*100);
number=rand()%N+1;
#endif
//开始输入到文件
printf("%d\n",1000);
for(int k=1;k<=1000;k++)
{
for(int j=1;j<=10000;j++)
{
number=rand()%N;
if(number>=97&&number<=122)
printf("%c",number);
}
printf("\n");
}
return 0;
}
|
运用重定向来测试到底会运行多长时间：
用下面这条语句来测试运行时间：
1
|
printf("\n\nTime used = %.0lf ms\n",(double)(1000*clock()/CLOCKS_PER_SEC));
|
直接在冒泡内进行字符串的交换，所花时间为：1702ms
使用指针排序所花的时间为：163ms
评测系统允许的时间最大为1s，显然是对的。
然后我就不说什么了。以后还是要有自身判断正误的能力。
