PAT 1047

题目 ： Student List for Course

分值 ： 25
难度 ： 时间题
思路 ： 搞个 vector<vecotr<string>> 比 vector<set<string>> 要快
       搞个 char[20040][5] 比  vector<vecotr<string>> 更快
坑点 ： 动不动就超时,  string -> array ( s.c_str()的使用 )
评语 ： 利用 cin cout 和stl 卡你时间

卡时间测试点 790ms 代码:

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
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<string>>db;
bool cmp(string a, string b)
{
    return a < b ;
}
int main()
{
    int N , K ,t , j ;
    string s;
    char ss[5];
    cin >> N >> K ;
    db.resize(K+1) ;
    for(int i = 0 ; i< N ; i++)
    {
        scanf("%s %d" , ss ,&j);
        s =ss ;
        for(int ii = 0 ; ii < j ;ii++)
        {
            scanf("%d",&t);
            db[t].push_back(s) ;
        }
    }
    for(int i = 1 ;i <= K ; i++)
    {
        printf("%d %d\n",i,db[i].size());
        sort(db[i].begin(),db[i].end(), cmp) ;
        for(int ia = 0 ; ia < db[i].size() ; ia++)
            printf("%s\n", (db[i][ia]).c_str()) ;
    }
}

卡时间测试点 400ms 代码:

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
#include <set>
#include <iostream>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
char name[40010][5] ;
vector< vector<int> > db;
bool cmp(int a, int b)
{
    return strcmp(name[a],name[b]) < 0 ;
}
int main()
{
    int N , K ,j ,t;
    cin >> N>> K ;
    db.resize(K+1 );
    for(int i = 0;i<  N ; i++)
    {
        scanf("%s %d" ,name[i], &j);
        for(int ii = 0 ; ii< j ;ii++)
        {
            scanf("%d",&t) ;
            db[t].push_back(i) ;
        }
    }
    for(int i = 1;i<=K ;i++ )
    {
        printf("%d %d\n" , i ,db[i].size()) ;
        sort(db[i].begin(),db[i].end(),cmp );
        for(int ia = 0 ; ia< db[i].size() ; ia++)
            printf("%s\n",name[db[i][ia]]);
    }

}