hdu2093题解

题目:

C++ 编程考试使用的实时提交系统,具有即时获得成绩排名的特点。它的功能是怎么实现的呢? 我们做好了题目的解答,提交之后,要么 “AC”,要么错误,不管怎样错法,总是给你记上一笔,表明你曾经有过一次错误提交,因而当你一旦提交该题 “AC” 后,就要与你算一算帐了,总共该题错误提交了几回。虽然你在题数上,大步地跃上了一个台阶,但是在耗时上要摊上你共花去的时间。特别是,曾经有过的错误提交,每次都要摊上一定的单位时间分。这样一来,你在做出的题数上,可能领先别人很多,但是,在做出同样题数的人群中,你可能会在耗时上处于排名的劣势。 例如:某次考试一共 8 题(A,B,C,D,E,F,G,H),每个人做的题都在对应的题号下有个数量标记,负数表示该学生在该题上有过的错误提交次数,但到现在还没有 AC,正数表示 AC 所耗的时间,如果正数 a 跟上一对括号,里面有个整数 b,那就表示该学生提交该题 AC 了,耗去了时间 a,同时,曾经错误提交了 b 次,因此对于下述输入数据:

hdu2093题解

若每次错误提交的罚分为 20 分,则其排名从高到低应该是这样的: Josephus 5 376 John 4 284 Alice 4 352 Smith 3 167 Bob 2 325 Bush 0 0

INPUT

输入数据的第一行是考试题数 n(1≤n≤12)以及单位罚分数 m(10≤m≤20),每行数据描述一个学生的用户名(不多于 10 个字符的字串)以及对所有 n 道题的答题现状,其描述采用问题描述中的数量标记的格式,见上面的表格,提交次数总是小于 100,AC 所耗时间总是小于 1000。

OUTPUT

将这些学生的考试现状,输出一个实时排名。实时排名显然先按 AC 题数的多少排,多的在前,再按时间分的多少排,少的在前,如果凑巧前两者都相等,则按名字的字典序排,小的在前。每个学生占一行,输出名字(10 个字符宽),做出的题数(2 个字符宽,右对齐)和时间分(4 个字符宽,右对齐)。名字、题数和时间分相互之间有一个空格。

Sample Input

8 20

Smith -1 -16 8 0 0 120 39 0

John 116 -2 11 0 0 82 55(1) 0

Josephus 72(3) 126 10 -3 0 47 21(2) -2

Bush 0 -1 -8 0 0 0 0 0

Alice -2 67(2) 13 -1 0 133 79(1) -1

Bob 0 0 57(5) 0 0 168 -7 0

Sample Output

Josephus 5 376

John 4 284

Alice 4 352

Smith 3 167

Bob 2 325

Bush 0 0

题目分析

有题目可以,我们需要计算出每名同学的罚时,以及AC的题数,并根据题数和罚时进行排序,排序规则如下:AC题数多的同学排前面,当AC题数相同,那么罚时越少的同学排前面,当AC题数相同,罚时也相同时,则按字典序排,小的在前面。

这里说明一下该题中比赛中罚时的计算方法:没有AC的题目不计算罚时,罚时=AC所用的时间+m*(已AC题目WA的次数)


如:72(2) 0 -9 80(3) 100

罚时=72+80+100+m*(2+3)


所以,分析完题目后目标就很明确了,将每个同学的罚时和AC题数计算出来,在根据排序规则排序即可。

由于每名同学包含的数据有多项,所以我们将同学所有的数据打包成一个类,再声明一个类的对象数组,这样会更加方便操作。

 
class Competor{
     public:
     Competor(){
         rank=0;
         time_score=0;
     }
     string name;
     int rank;
     int time_score;
 };
当类构建好后,接下来要考虑的就是如何将数据信息输入到类的对象中。

我的方法是利用cin >> string类对象 进行输入,再利用字符-'0'的方式将字符转换成数值。为什么利用cin>>输入,因为当利用 cin 输入时可以自动过滤掉数据之间的空格。

输入后数据后我们可以进行简单的判断,将包含'-'(负号),'0'的数据过滤,因为它们并不参与时间分的计算。

过滤之后,我们要将string类的对象转换成数值。这一部分是最麻烦的,因为有的对象中无括号(),而有的有。

所以我们利用string类中的find()函数,判断是否存在括号,并找出括号的位置,再进行计算。

 Competor racer[1000];
     int n,m,p=0;//p是队友总数
     cin >> n >> m;
     string score;
     cin.get();//输入数字后再输入字符,需要cin.get()吃掉换行符
     while(cin >> racer[p].name){
         for(int i=0;i<n;i++){
             cin >> score;
             //进行判断
             if(score[0]=='-'||score[0]=='0'){
                 continue;
             }
             //利用find函数,查找是否有括号,有则pos1,pos2是括号的位置,若没有,则都为-1
             int pos1=score.find('(');
             int pos2=score.find(')');
             //判断是否存在括号,若存在,则对括号内WA次数进行罚时计算
             if(pos1!=-1&&pos2!=-1){
                 if(pos2-pos1==2){
                     racer[p].time_score+=(score[pos1+1]-'0')*m;//字符转化成数值
                 }
                 else if(pos2-pos1==3){
                     racer[p].time_score+=((score[pos1+1]-'0')*10+(score[pos1+2]-'0'))*m;
                 }                
             }
             //再对AC的时间进行计算
             for(int o=0;o<score.length();o++){
                 if(score[o]==' ') break;
                 if(o==pos1) break;
                 
                 if(pos1!=-1){
                     racer[p].time_score+=pow(10.0,pos1-1-o)*(score[o]-'0');
                 }
                 else racer[p].time_score+=pow(10.0,score.length()-1-o)*(score[o]-'0');
             }
             //记录AC的题数
             racer[p].rank++;
         }
         p++;
         //吃掉换行符
         cin.get();
当数据输入好后,我们需要按照我们的规则对数组内的对象进行重新排序,这时要利用到sort函数,并且要说明排序规则rule 
//制定规则
 bool rule(const Competor &a1,const Competor &a2){
         if(a1.rank!=a2.rank){
             return a1.rank>a2.rank;
         }
         else if(a1.time_score!=a2.time_score){
             return a1.time_score<a2.time_score;
         }
         else{
             return a1.name<a2.name;
         }
 }
 //进行排序
 sort(racer,racer+p,rule);
最后根据题中的格式进行输出即可

全部代码:

 #include<iostream>
 #include<string.h>
 #include<cmath>
 #include<algorithm>
 #include<iomanip>
 #include<string>
 using namespace std;
 class Competor{
     public:
     Competor(){
         rank=0;
         time_score=0;
     }
     string name;
     int rank;
     int time_score;
 };
 bool rule(const Competor &a1,const Competor &a2){
         if(a1.rank!=a2.rank){
             return a1.rank>a2.rank;
         }
         else if(a1.time_score!=a2.time_score){
             return a1.time_score<a2.time_score;
         }
         else{
             return a1.name<a2.name;
         }
 }
 int main(){
     Competor racer[1000];
     int n,m,p=0;//p是队友总数
     cin >> n >> m;
     string score;
     cin.get();
     while(cin >> racer[p].name){
         for(int i=0;i<n;i++){
             cin >> score;
             if(score[0]=='-'||score[0]=='0'){
                 continue;
             }
             int pos1=score.find('(');
             int pos2=score.find(')');
             if(pos1!=-1&&pos2!=-1){
                 if(pos2-pos1==2){
                     racer[p].time_score+=(score[pos1+1]-'0')*m;
                 }
                 else if(pos2-pos1==3){
                     racer[p].time_score+=((score[pos1+1]-'0')*10+(score[pos1+2]-'0'))*m;
                 }                
             }
             for(int o=0;o<score.length();o++){
                 if(score[o]==' ') break;
                 if(o==pos1) break;
                 
                 if(pos1!=-1){
                     racer[p].time_score+=pow(10.0,pos1-1-o)*(score[o]-'0');
                 }
                 else racer[p].time_score+=pow(10.0,score.length()-1-o)*(score[o]-'0');
             }
             racer[p].rank++;
         }
         p++;
         cin.get();
     }
     
     sort(racer,racer+p,rule);
     for(int i=0;i<p;i++){
         cout << setw(10) << left << racer[i].name ;
         cout << setw(3) << right  << racer[i].rank ;
         cout <<  setw(5) << right << racer[i].time_score <<endl;
     }
     return 0;
 }

新手文章,欢迎大佬批评改正!

上一篇:网站建设——部署与发布入门篇(基于阿里云服务器)


下一篇:《Total Commander:万能文件管理器》——导读