我的解法
解题思路：这道题目本身不难，比较简单，边读取边排序，然后合并到一个vector上，并进行总排序，在排序和读取的过程中完善结构体！但是这道题目有一个巨坑！就是注册学号可能是0开头的，所以一开始使用long long代表学号在打印的时候要注意前面补0，后来我换成了char 字符数组来表示！全部通过！
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
75
76
77
78
| #include <iostream>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxn=105;
int n;
int lnums[maxn];
struct Stu{
char num[15];
int frank;
int loc;
int lrank;
int score;
};
bool cmp(Stu a,Stu b){
if(a.score!=b.score) return a.score>b.score;
else return strcmp(a.num,b.num)<=0;
}
int main(){
cin>>n;
vector<Stu> pre_vec;
for(int i=0;i<n;i++){
cin>>lnums[i];
vector<Stu> vec;
for(int j=0;j<lnums[i];j++){
Stu s;
cin>>s.num>>s.score;
s.loc=i+1;
vec.push_back(s);
}
sort(vec.begin(),vec.end(),cmp);
vec[0].lrank=1;
int l=vec.size();
for(int k=1;k<l;k++){
if(vec[k-1].score==vec[k].score){
vec[k].lrank=vec[k-1].lrank;
}else{
vec[k].lrank=k+1;
}
}
vector<Stu> d_vec(vec.size()+pre_vec.size());
merge(vec.begin(),vec.end(),pre_vec.begin(),pre_vec.end(),d_vec.begin(),cmp);
d_vec.swap(pre_vec);
}
int total=0;
for(int i=0;i<n;i++) total+=lnums[i];
cout<<total<<endl;
pre_vec[0].frank=1;
int pl=pre_vec.size();
for(int k=1;k<pl;k++){
if(pre_vec[k-1].score==pre_vec[k].score){
pre_vec[k].frank=pre_vec[k-1].frank;
}else{
pre_vec[k].frank=k+1;
}
}
for(int i=0;i<pl;i++){
cout<<pre_vec[i].num<<" "<<pre_vec[i].frank<<" "<<pre_vec[i].loc<<" "<<pre_vec[i].lrank<<endl;
}
return 0;
}
|
算法笔记解法
解题思路：使用数组，定义int型变量num，用来存放当前获取到考生人数。每读入一个考生的信息，就让num自增。这样每当读取完一个考场的考生信息(假设该考场有k个考生)后，这个考场的考生所对应的数组下标便为区间[num-k,num)。
使用数组的时间复杂度比用vector以及merge排序合并要快了3倍左右。数组最长时间为42ms，我的解法是142ms左右。
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
| #include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
struct Stu{
char id[15];
int frank;
int loc;
int lrank;
int score;
};
Stu stus[30010];
bool cmp(Stu a,Stu b){
if(a.score!=b.score) return a.score>b.score;
else return strcmp(a.id,b.id)<=0;
}
int main(){
int n,num=0;
scanf("%d",&n);
for(int i=1;i<=n;i++){
int m;
scanf("%d",&m);
for(int j=0;j<m;j++){
scanf("%s%d",stus[num].id,&stus[num].score);
stus[num].loc=i;
num++;
}
sort(stus+num-m,stus+num,cmp);
stus[num-m].lrank=1;
for(int j=1;j<m;j++){
if(stus[num-m+j].score==stus[num-m+j-1].score)
stus[num-m+j].lrank=stus[num-m+j-1].lrank;
else stus[num-m+j].lrank=j+1;
}
}
sort(stus,stus+num,cmp);
stus[0].frank=1;
for(int j=1;j<num;j++){
if(stus[j].score==stus[j-1].score)
stus[j].frank=stus[j-1].frank;
else stus[j].frank=j+1;
}
printf("%d\n",num);
for(int i=0;i<num;i++){
printf("%s %d %d %d\n",stus[i].id,stus[i].frank,stus[i].loc,stus[i].lrank);
}
return 0;
}
|