比赛记分问题 - 无幻の编程 - 对于一个初学者来说,野心也是必须的...

比赛记分问题

无幻 posted @ 2009年6月08日 02:30 in 算法结构 with tags c++ 算法 数据结构 , 1663 阅读

 

问题描述:
在ACM/ICPC地区赛中,每次解答程序的提交叫做一次提交。每次提交的程序或者被判接受或者被判退回,而每个参赛队伍将会得到提交的结果。队伍将按照做对题目的多少排名,为了奖励优秀队伍或确定进入世界总决赛的资格名单,做出相同题目数量的队伍将被按照做出题目的时间和惩罚时间的从少到多排名。总的解题时间和惩罚时间就是每个已解决问题所需要的时间之和。一道题目的解决时间就是指从开始做一道题到一道题目的成功提交的时间加上提交一次失败而惩罚20分钟的时间。对于没解决的题目不计时。
你的程序将读入一张运行结果清单。然后打印出第1,2,3名的成绩。
输入:
输入文件包含若干测试数据集。
每个测试数据由两个部分组成。第一部分包含一个正整数,它表示参赛队伍的个数。接下来的几行是每次提交的结果。每行表示一次提交的结果,包括提交时间,队伍编号,问题编号和裁定结果。测试数据由单独占一行的0结束。输入文件的最后一行只有一个0.
输出:
输出前三名的比分,包括队号,做出题数,比赛用时,名次。
假设:可能有好几队在同一名次。比如,如果有几队都是第三名刚它们全部输出;如果有两队是第二名,刚没有第三名,等等。
输入范例:(input1.txt)
3
12 1 2 yes
14 3 2 no
25 3 1 yes
29 1 1 no
38 3 2 yes
39 2 1 no
45 1 1 no
0
输出范例:
Team No.    problem solved     time used    rank
3                             2                          83               1
1                             1                          12               2
2                             0                            0               3

 

 

#include <iostream>
#include <fstream>
#include <string>
using namespace std;


const int N=100;
struct infoTeam
{
        int timeNeed;      //提交时间     
        int teamNumber;  //队伍编号
        int questionNumber; //问题编号
        string answer;    //裁定结果
};
struct winTeam
{
        int teamNo;               //队伍编号
        int timeUsed;      //提交时间
        int  problemSolved;     //问题解决数量
        int errorTime;    //错误次数
        int rank;                     //排名
};
int max(int a,int b)       
{
        return (a > b)? a : b;
} 
int main()
{
        int numberTeam;   //总共的参赛队伍
        int countNote=0;                //总共的提交数量
        int maxQuestion=0;            //最大的问题编号

        struct infoTeam p[N];
        struct winTeam q[N];
        ifstream cin1("inputtest1.dat");
        cin1>>numberTeam;
        for (int i=0;i<N && !cin1.eof() ;i++)
        {
                cin1>>p[i].timeNeed>>p[i].teamNumber>>p[i].questionNumber>>p[i].answer;
                if (p[i].timeNeed==0)
                {
                        break;
                }              
                countNote++;
        }
        for (i=0;i<countNote;i++)
        {
                maxQuestion=max(maxQuestion,p[i].questionNumber);
        }
        for (i=0;i<N;i++)
        {
                q[i].problemSolved=0;
                q[i].timeUsed=0;
                q[i].errorTime=0;
                q[i].rank=numberTeam;
        }
        /**********************************************************
         **********************************************************
         ****循环整个提交队列,再按各队编号遍历           **
         ****判定每次提交的是哪个队伍,再对这次的提交进行处理           **
         ****判定处理的是哪个问题,再对裁定结果进行处理                   **
         ****判定裁定结果正确与否,若是对的,则计算当前队伍的比赛用时 **
         ****若是错的,则错误次数要被加1                                    **
         **********************************************************
        */

        for (i=0;i<countNote;i++)                                                        //循环整个提交队列
        {
                for (int j=1;j<=numberTeam;j++)      //循环整个队伍队列
                {
                        q[j].teamNo=j;                  //队伍编号升序初始化
                        if (p[i].teamNumber==j)                   //处理当前队伍编号
                        {                            
                                for (int k=1;k<=maxQuestion;k++)              //处理当前队伍提交问题的判定
                                {
                                        if (p[i].questionNumber==k)                    //处理当前题号
                                        {
                                                if (p[i].answer=="yes")    //裁定结果正确
                                                {
                                                        //当前队伍的比赛用时=累计比赛用时+此时提交用时+惩罚时间
                                                        q[j].timeUsed=q[j].timeUsed+p[i].timeNeed+q[j].errorTime*20;
                                                        q[j].errorTime=0;                            //错误标识置0
                                                        q[j].problemSolved++;         //问题解决数递加
                                                }
                                                else
                                                {                                                 
                                                        q[j].errorTime++;                            //错误标识递加
                                                }
                                        }
                                }
                        }
                }
        }
        /************************************************************************/
        /* 冒泡法排序,将各队名次降序排列                                        */
        /* 按照解题的数目降序排列,第二关键字解题时间升序排列
        /************************************************************************/

        int exchange=numberTeam;                //第一趟起泡排序的范围是队伍总数量
        int bound;                                    //无序区的最后一个记录
        while (exchange)                                //仅当上一趟排序有记录交换才进行本趟排序
        {
                bound=exchange;
                exchange=0;
                for (i=1;i<bound;i++)            //一趟起泡排序
                {                     
                        if (q[i].problemSolved>q[i+1].problemSolved)
                        {       
                                q[N-1]=q[i];
                                q[i]=q[i+1];
                                q[i+1]=q[N-1];
                                exchange=i;               //记录每一次发生记录交换的位置
                        }
                        else if (q[i].problemSolved==q[i+1].problemSolved)
                        {
                                if (q[i].timeUsed<q[i+1].timeUsed)
                                {
                                        q[N-1]=q[i];
                                        q[i]=q[i+1];
                                        q[i+1]=q[N-1];
                                        exchange=i;
                                }
                        }
                }
        }
        /************************************************************************/
        /* 对已经排好序的队伍,进行名次的判定                                   */
        /************************************************************************/
        cout<<"Team No.  "<<"problem solved     "<<"time used         "<<"rank"<<endl;
        for (i=1;i<=numberTeam;i++)
        {
                q[i].rank=q[i-1].rank-1;                //因为队伍已按评分标准重列队伍编号了,假定排名无重复,则依队伍编号降序排列
        }
        //逆序循环,找出前三名的队伍,若做出题数,比赛用时都一样,则排名一致.
        for (i=numberTeam;i>0;i--)
        {
                if (q[i].problemSolved==q[i+1].problemSolved)
                {
                       
                        if (q[i].timeUsed==q[i+1].timeUsed)
                        {
                                q[i].rank=q[i+1].rank
                        }
                }
                if (q[i].rank>2)
                {
                        break;
                }
                cout<<q[i].teamNo<<"\t\t"<<q[i].problemSolved<<"\t\t"<<q[i].timeUsed<<"\t\t"<<q[i].rank+1<<endl;
        }
        return 0;
}

 


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee