按照学生的选课情况，输出这门课有哪些学生上，并按字幕顺序输出。
注意，无论这个课有没有人上都要打印课程号和人数。
这个题通过对学生姓名的处理有两种方法。
一种是用字符数组来存名字，来避免string的超时问题。将字符数组放在结构体里面然后用vector类来排序处理。
#include <iostream> #include <vector> #include <string> #include <algorithm> #include <map> #include <queue> #include <stack> #include <cstring> #define MAXN 40010 #define MAXK 2510 using namespace std; struct Node{ char name[5]; }; int n,k; Node list[MAXN]; vector <Node> cla[MAXK]; bool cmp(Node n1,Node n2){ return strcmp(n1.name,n2.name) < 0; } int main(){ scanf("%d%d",&n,&k); int m,no; string name; for(int i = 0 ; i< n ;i++){ scanf("%s %d",list[i].name,&m); for(int j = 0 ; j < m ;j++){ scanf("%d",&no); cla[no].push_back(list[i]); } } for(int i = 1 ; i <= k ;i++){ printf("%d %d\n",i,cla[i].size());//无论是否有学生都要显示课程号和人数 if(cla[i].size()!= 0){ sort(cla[i].begin(),cla[i].end(),cmp); for(int j = 0 ; j < cla[i].size() ;j++){ printf("%s\n",cla[i][j].name); } } } return 0 ; }另外一种是照样用string。因为题目里面已经说了名字只有4位..所以我们就把名字转化为一个整数。开个26*26*26*10+10 大概17W还是能接受的数组来换时间。PAT里面有不少题可以这么玩。这样还能大大减少排序比较时候的时间。
可以看看时间差的还是挺多的。
#include <iostream> #include <string> #include <vector> #include <algorithm> #include <map> #define MAXN 40010 #define MAXK 2510 #define MAXNMAME 26*26*26*10+10 using namespace std; vector <int> sub[MAXK]; int Hash[MAXNMAME]; int N, K; char * name[MAXN]; int name2int(char * c) { return int(c[0] - 'A') * 26 * 26 * 10 + int(c[1] - 'A') * 26 * 10 + int(c[2] - 'A') * 10 + int(c[3] - '0'); } bool cmp(int n1, int n2) { return n1 < n2; } int main() { cin >> N >> K; int num; string s; s.resize(4); int temp; for (int i = 0; i < N; i++) { char * n = new char[4]; scanf("%s %d", n, &num); int no = name2int(n); Hash[no] = i; name[i] = n; for (int j = 0; j < num; j++) { scanf("%d", &temp); sub[temp].push_back(no); } } for (int i = 1; i <= K; i++) { printf("%d %d\n",i,sub[i].size()); if (sub[i].size() != 0) { sort(sub[i].begin(), sub[i].end(),cmp); for (int j = 0; j < sub[i].size(); j++) { printf("%s\n",name[Hash[sub[i][j]]]); } } } return 0; }
