pat排序问题

排序问题一般是给定一组数据让你根据规则进行排序，其中应用比较广的就是cmp排序规则和排名rank的计算

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805474338127872

 1 //需要注意的几个点
 2 //排序的规则是现根据成绩大小排名，在根据学号从小到达排
 3 //每一场的场内排序需要注意，不要忘记-k+cnt;
 4 //每一次输入的是p[cnt]，方便到了最后输出
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=1e2+10;
10 struct node
11 {
12     int location_num;
13     char id[13];
14     int rk;
15     int sc;
16 }p[N];
17 int n;
18 int k;
19 int cnt;
20 bool cmp(node a,node b)
21 {
22     if(a.sc!=b.sc)
23     return a.sc>b.sc;
24     else
25     {
26         return strcmp(a.id,b.id)<0;
27     }
28 }
29 signed main()
30 {
31     IOS;
32     cin>>n;
33     for(int i=1;i<=n;i++)
34     {
35         cin>>k;
36         for(int j=0;j<k;j++)
37         {
38             cin>>p[cnt].id>>p[cnt].sc;
39             p[cnt].location_num=i;
40             cnt++;
41         }
42         sort(p+cnt-k,p+cnt,cmp);//注意
43         p[cnt-k].rk=1;//注意cnt-k;
44         for(int q=cnt-k+1;q<cnt;q++)
45         {
46             if(p[q].sc==p[q-1].sc)
47             {
48                 p[q].rk=p[q-1].rk;
49             }
50             else
51             {
52                 p[q].rk=q+1-(cnt-k);//注意减去(cnt-k);
53             }
54         }
55         
56     }
57     cout<<cnt<<endl;
58     sort(p,p+cnt,cmp);
59     int r=1;
60     for(int i=0;i<cnt;i++)
61     {
62         if(i>0&&p[i].sc!=p[i-1].sc)
63         {
64             r=i+1;
65         }
66         cout<<p[i].id<<" "<<r<<" "<<p[i].location_num<<" "<<p[i].rk;
67         if(i<cnt-1)
68         cout<<endl;
69     }
70     return 0;
71 }

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805468327690240

 1 //注意一个坑点，ch那里不要设成8，不要设成8，不要设成8
 2 #include<bits/stdc++.h>
 3 using namespace std;
 4 #define int long long 
 5 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 6 const int N=1e5+10;
 7 struct node
 8 {
 9     int id;
10     char ch[10];
11     int g;
12 }stu[N];
13 int n,c;
14 bool cmp(node a,node b)
15 {
16     if(c==1)
17     {
18         return a.id<b.id;
19     }
20     if(c==2)
21     {
22         if(strcmp(a.ch,b.ch)!=0)
23         return strcmp(a.ch,b.ch)<0;
24             return a.id<b.id;
25     }
26     if(c==3) 
27     {
28         if(a.g!=b.g)
29         return a.g<b.g;
30         return a.id<b.id;
31     }
32 }
33 signed main()
34 {
35     //IOS;
36     cin>>n>>c;
37     for(int i=0;i<n;i++)
38     {
39         cin>>stu[i].id>>stu[i].ch>>stu[i].g;
40     }
41     sort(stu,stu+n,cmp);
42     for(int i=0;i<n;i++)
43     {
44         printf("%06lld ",stu[i].id);
45         cout<<stu[i].ch<<" "<<stu[i].g;
46         if(i<n-1)
47             cout<<endl;
48     }
49     return 0;
50 }

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805425780670464

 1 //需要注意的几个点
 2 //排序的方式是按照节点的有效性和节点键值的大小进行排序的
 3 //输入的时候索引是节点的地址
 4 //排序的时候注意le+N,不是+cnt，因为由于有效性的分布使得有效的在左边，但是按照索引地址的输入使得
 5 //分布较为分散，所以说要对范围内的节点进行排序
 6 #include<bits/stdc++.h>
 7 using namespace std;
 8 #define int long long 
 9 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
10 const int N=1e5+10;
11 struct node
12 {
13     int ad;
14     int key;
15     int ne;
16     int flag;
17 }le[N];
18 int n,st;
19 int cnt;
20 bool cmp(node a,node b)
21 {
22     if(a.flag!=b.flag)
23     return a.flag>b.flag;
24     else
25     {
26         return a.key<b.key;
27     }
28 }
29 signed main()
30 {
31     //IOS;
32     cin>>n>>st;
33     int a,b,c;
34     for(int i=0;i<n;i++)
35     {
36         cin>>a>>b>>c;
37         le[a].ad=a;//索引是节点的地址
38         le[a].key=b;
39         le[a].ne=c;
40     }
41     for(int i=st;~i;i=le[i].ne)
42     {
43         cnt++;
44         le[i].flag=1;
45     }
46     if(cnt==0)
47     {
48         cout<<0<<" "<<-1;
49     }
50     else
51     {
52         sort(le,le+N,cmp);
53         printf("%lld %05lld\n",cnt,le[0].ad);
54         for(int i=0;i<cnt;i++)
55         {
56             if(i<cnt-1)
57             {
58                 printf("%05lld %lld %05lld\n",le[i].ad,le[i].key,le[i+1].ad);
59             }
60             else
61             {
62                 printf("%05lld %lld -1",le[i].ad,le[i].key);
63             }
64         }
65     }
66     return 0;
67 }

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805447855292416

 1 //需要注意的几个点
 2 //字符串哈希的应用
 3 //v.size的判断
 4 //对于选课人员的序号升序排序
 5 #include<bits/stdc++.h>
 6 using namespace std;
 7 #define int long long 
 8 #define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 9 const int N=4e4+10;
10 const int M=26*26*26*10+1;
11 int n,k;
12 vector<int>v[M];
13 int getid(string s)
14 {
15     int id=0;
16     for(int i=0;i<3;i++)
17     {
18         id=id*26+(s[i]-'A');
19     }
20     id=id*10+(s[3]-'0');
21     return id;
22 }
23 signed main()
24 {
25     IOS;
26     cin>>n>>k;
27     while(k--)
28     {
29         string s;
30         int id,num;
31         cin>>id>>num;
32         for(int i=0;i<num;i++)
33         {
34             cin>>s;
35             int d=getid(s);
36             v[d].push_back(id);
37         }
38     }
39     string q;
40     for(int i=1;i<=n;i++)
41     {
42         cin>>q;
43         int d=getid(q);
44         sort(v[d].begin(),v[d].end());
45         cout<<q<<" ";
46         if(v[d].size())
47         {
48             cout<<v[d].size()<<" ";
49         }
50         else
51         {
52             cout<<v[d].size();
53         }
54         for(int j=0;j<v[d].size();j++)
55         {
56             cout<<v[d][j];
57             if(j<v[d].size()-1)
58                 cout<<" ";
59         }
60         cout<<endl;
61     }
62     return 0;
63 }

https://pintia.cn/problem-sets/994805342720868352/exam/problems/994805433955368960

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 //#define IOS ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
 5 const int N=4e4+10;
 6 vector<int>v[2510];
 7 char name[N][5];
 8 int n,k;
 9 int num;
10 bool cmp(int a,int b )
11 {
12     return strcmp(name[a],name[b])<0;
13 }
14 signed main()
15 {
16     //IOS;
17     ios::sync_with_stdio(false);
18     cin>>n>>k;
19     for(int i=0;i<n;i++)
20     {
21         int num;
22         cin>>name[i]>>num;
23         int tmp;
24         for(int j=0;j<num;j++)
25         {
26             cin>>tmp;
27             v[tmp].push_back(i);
28         }
29     }
30     for(int i=1;i<=k;i++)
31     {
32         cout<<i<<" "<<v[i].size()<<endl;
33         sort(v[i].begin(),v[i].end(),cmp);
34         for(int j=0;j<v[i].size();j++)
35         {
36             cout<<name[v[i][j]]<<endl;
37         }
38     }
39     return 0;
40 }