浙大数据结构：10-排序5 PAT Judge

这道题也有点难度，主要是输出要求太多了
机翻

1、条件准备

N,K,M是学生数量，题目数量，提交数量。
score数组存每道题的满分。
student二维数组存编号为i的学生每道题的得分情况，ifsubmit二维数组存每个学生的每个题目是否提交了，主要后面用来判断输出方式的。
studentrank数组存学生的分数和其它因素权重和，后面再说。
再设定三个常数，为了studentrank数组用到

#include <iostream>
#include<iomanip>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int N,K,M;
int score[6];
int student[10005][6];
bool ifsubmit[10005][6];
vector<long long> studentrank;
const long long LL1e8=100000000;
const long long  LL1e7=10000000;
const long long LL1e6=1000000;

2、主函数

先初始化，再初始化rank排名，再输出打印

int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init();initrank();Print();return 0;
}

3、init函数

输入数据，输入每道题的满分。
再输入每次提交的数据ifsubmit数组置1，
编号s的student的第problem个问题的得分与本身取max。
由于初始化为-1，如果编译没通过则仍为-1.

void init()
{
cin>>N>>K>>M;memset(student,-1,sizeof(student));for(int i=1;i<=K;i++)cin>>score[i];for(int i=0;i<M;i++){int s,problem,sco;cin>>s>>problem>>sco;ifsubmit[s][problem]=1;student[s][problem]=max(student[s][problem],sco); }
}

4、initrank函数

遍历每个学生，sum表示总分数，perfect表示满分的题目数量，f表示是否提交并且编译通过，否则这位学生最后是不输出的。
我们把每个学生的相关情况按不同权重来组合到一起，开long long ，数字比较大。
后面直接用sort函数能直接排好序我们输出即可。
sum是得分1e8,它的权重最高，一定是优先按得分排序，再加上perfect1e6，如果得分一样看满分的数量，
再减i表示该学生的id，因为如果前面一样，那么id小的先输出，这里我们是从小到大排序，输出的时候从后往前输出，所以id小综合权重大，我们就取负的就行了。但是这里还要考虑高位减1的情况，减的时候低位是0，要从高位取1，会影响值，所以我们加1e7来解决，那么排好序后就从后往前输出即可，后面再看我怎么用

void initrank()
{for(int i=1;i<=N;i++){int sum=0, perfect=0,f=0;for(int j=1;j<=K;j++){if(student[i][j]==-1)continue;f=1;sum+=student[i][j];if(student[i][j]==score[j])perfect++;}if(!f)continue;long long ran=sum*LL1e8+perfect*LL1e6-i+LL1e7;studentrank.push_back(ran);}sort(studentrank.begin(),studentrank.end());
}

5、Print函数

Rank表示排名，old表示上一名学生的分数，stunum表示这是第几个学生。
我们先取出该学生的总分数，和id号。
也就是/1e8即可，然后对1e7取模，再除以1e6再加上1算得满分题目数量，则学生id为满分数量*1e6-取模完的studentrank[i]。这个地方我感觉我设计的有点巧妙，没弄懂的话可以再这输出数据看看。
如果得分与上一个学生不一样则排名为学生数量，否则排名跟上一名学生一样。
然后就是输出了，注意末尾无多余空格，这个输出要求也够多的。
注意如果得分为-1看看他是否提交过，提交过输出0否则输出-。

void Print()
{int Rank=0; int old=0; int stunum=0;for(int i=studentrank.size()-1;i>=0;i--){stunum++;int sum=studentrank[i]/LL1e8;studentrank[i]%=LL1e7;int perfect=studentrank[i]/LL1e6+1;int id=perfect*LL1e6-studentrank[i];if(sum!=old) Rank=stunum;old=sum;cout<<Rank<<' '<<setw(5)<<setfill('0')<<id;cout<<' '<<sum;for(int i=1;i<=K;i++){if(student[id][i]==-1){if(ifsubmit[id][i])cout<<" 0";else cout<<" -";}else cout<<' '<<student[id][i];}cout<<endl;}
}

6、总结

这道题目我采用对属性加权再排序的方式，我感觉还是较好理解也比较方便的
完整代码如下

#include <iostream>
#include<iomanip>
#include<string.h>
#include<vector>
#include<algorithm>
using namespace std;
#define endl '\n'int N,K,M;
int score[6];
int student[10005][6];
bool ifsubmit[10005][6];
vector<long long> studentrank;
const long long LL1e8=100000000;
const long long  LL1e7=10000000;
const long long LL1e6=1000000;
void init()
{
cin>>N>>K>>M;memset(student,-1,sizeof(student));for(int i=1;i<=K;i++)cin>>score[i];for(int i=0;i<M;i++){int s,problem,sco;cin>>s>>problem>>sco;ifsubmit[s][problem]=1;student[s][problem]=max(student[s][problem],sco); }
}void initrank()
{for(int i=1;i<=N;i++){int sum=0, perfect=0,f=0;for(int j=1;j<=K;j++){if(student[i][j]==-1)continue;f=1;sum+=student[i][j];if(student[i][j]==score[j])perfect++;}if(!f)continue;long long ran=sum*LL1e8+perfect*LL1e6-i+LL1e7;studentrank.push_back(ran);}sort(studentrank.begin(),studentrank.end());
}
void Print()
{int Rank=0; int old=0; int stunum=0;for(int i=studentrank.size()-1;i>=0;i--){stunum++;int sum=studentrank[i]/LL1e8;studentrank[i]%=LL1e7;int perfect=studentrank[i]/LL1e6+1;int id=perfect*LL1e6-studentrank[i];if(sum!=old) Rank=stunum;old=sum;cout<<Rank<<' '<<setw(5)<<setfill('0')<<id;cout<<' '<<sum;for(int i=1;i<=K;i++){if(student[id][i]==-1){if(ifsubmit[id][i])cout<<" 0";else cout<<" -";}else cout<<' '<<student[id][i];}cout<<endl;}
}
int main()
{std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);init();initrank();Print();return 0;
}