SDUT 3404 数据结构实验之排序七：选课名单.！？

数据结构实验之排序七：选课名单

Time Limit: 1000MS Memory Limit: 65536KB

Problem Description

随着学校规模的扩大，学生人数急剧增加，选课名单的输出也成为一个繁重的任务，我校目前有在校生3万多名，两千多门课程，请根据给定的学生选课清单输出每门课的选课学生名单。

Input

输入第一行给出两个正整数N( N ≤ 35000)和M(M ≤ 2000)，其中N是全校学生总数，M是课程总数，随后给出N行，每行包括学生姓名拼音+学号后两位(字符串总长度小于10)、数字S代表该学生选课的总数，随后是S个课程编号，约定课程编号从1到M，数据之间以空格分隔。

Output

按课程编号递增的顺序输出课程编号、选课总人数以及选课学生名单，对选修同一门课程的学生按姓名的字典序输出学生名单。数据之间以空格分隔，行末不得有多余空格。

Example Input

5 3
Jack01 2 2 3
Jone01 2 1 3
Anni02 1 1
Harry01 2 1 3
TBH27 1 1

Example Output

1 4
Anni02
Harry01
Jone01
TBH27
2 1
Jack01
3 3
Harry01
Jack01
Jone01

DQE:

sort函数的用法，第一个第二个参数构成排序区间为左闭右开[beg,end)，比较类型不明确，抽空仔细看看！

本题可以用以课程编号为下标的（学生信息链表数组）来解决，可以避免内存超限。

以下代码为避免超出减少了动态分配数组内存。

 1 #include <iostream>
 2 #include <string>
 3 #include <algorithm>    //sort头文件
 4 #include <cstdio>
 5 using namespace std;
 6 
 7 string **f;
 8 int num[2010];
 9 
10 int cmp(string a,string b)
11 {
12     return a<b;
13 }
14 
15 int main()
16 {
17     int n,m;
18     while(scanf("%d %d",&n,&m)!=EOF)
19     {
20         int i,j,k,s;
21         f=new string *[m+1];
22         for(i=1;i<=m;i++)
23             f[num[i]=0,i]=new string[m+1];    //这里不能申请n大小的空间不然必超出内存限制！！？？
24         for(i=1;i<=n;i++)
25         {
26             string temp;
27             cin>>temp>>s;
28             for(j=1;j<=s;j++)
29             {
30                 cin>>k;
31                 f[k][++num[k]]=temp;
32             }
33         }
34         for(i=1;i<=m;i++)
35         {
36             printf("%d %d
",i,num[i]);
37             sort(f[i]+1,f[i]+num[i]+1,cmp);
38             for(j=1;j<=num[i];j++)
39                 cout<<f[i][j]<<endl;
40             delete []f[i];
41         }
42         delete []f;
43     }
44     return 0;
45 }
46 
47 /***************************************************
48 User name: ***
49 Result: Accepted
50 Take time: 292ms
51 Take Memory: 36184KB
52 Submit time: 2016-12-09 19:57:14
53 ****************************************************/