首页 > ACM题库 > HDU-杭电 > HDU 2778-HOJ-LCR-模拟-[解题报告]C++
2014
02-14

HDU 2778-HOJ-LCR-模拟-[解题报告]C++

LCR

问题描述 :

LCR is a simple game for three or more players. Each player starts with three chips and the object is to be the last person to have any chips. Starting with Player 1, each person rolls a set of three dice. Each die has six faces, one face with an L, one with a C, one with an R and three with a dot. For each L rolled, the player must pass a chip to the player on their left (Player 2 is considered to be to the left of Player 1); for each R rolled, the player passes a chip to the player on their right; and for each C rolled, the player puts a chip in a central pile which belongs to no player. No action is taken for any dot that is rolled. Play continues until only one player has any chips left. In addition, the following rules apply:

1. A player with no chips is not out of the game, since they may later gain chips based on other players’ rolls.
2. A player with only 1 or 2 chips left only rolls 1 or 2 dice, respectively. A player with no chips left does not roll but just passes the dice to the next player.

Your job is to simulate this game given a sequence of dice rolls.

输入:

Input will consist of multiple test cases. Each test case will consist of one line containing an integer n (indicating the number of players in the game) and a string (specifying the dice rolls). There will be at most 10 players in any game, and the string will consist only of the characters `L’, `C’, `R’ and `.’. In some test cases, there may be more dice rolls than are needed (i.e., some player wins the game before you use all the dice rolls). If there are not enough dice rolls left to complete a turn (for example, only two dice rolls are left for a player with 3 or more chips) then those dice rolls should be ignored. A value of n = 0 will indicate end of input.

输出:

Input will consist of multiple test cases. Each test case will consist of one line containing an integer n (indicating the number of players in the game) and a string (specifying the dice rolls). There will be at most 10 players in any game, and the string will consist only of the characters `L’, `C’, `R’ and `.’. In some test cases, there may be more dice rolls than are needed (i.e., some player wins the game before you use all the dice rolls). If there are not enough dice rolls left to complete a turn (for example, only two dice rolls are left for a player with 3 or more chips) then those dice rolls should be ignored. A value of n = 0 will indicate end of input.

样例输入:

3 LR.CCR.L.RLLLCLR.LL..R...CLR. 
5 RL....C.L 
0

样例输出:

Game 1: 
Player 1:0 
Player 2:0 
Player 3:6(W) 
Center:3 

Game 2: 
Player 1:1 
Player 2:4 
Player 3:1 
Player 4:4(*) 
Player 5:4 
Center:1

题意:模拟CPU处理多个任务的过程。首先输入任务数n,然后下面n行每行对应一个任务的信息:任务id,到达CPU的时间,处理它所需要的时间,优先级。一个任务在处理过程中,如果有下一个任务到达并且该任务优先级高于正在处理的任务,则要中止当前任务,转而进行下个任务。若是两任务优先级相同,先执行先到达的任务。

大致思想:用了两个优先级队列,一个用来存储用户的输入,另一个用来存储已经到达的,正在等待中的任务。还有一个timer记录时钟。

详细的参见代码及注释。

//用STL里的priority_queue存储,剩下的就是模拟了。。
#include <iostream>
#include <cstdio>
#include <memory.h>
#include <queue>
#define INF 0x7fffffff
using namespace std;

struct Process
{
    int id;
    int arr;    //到达时间
    int last;
    int prior;
};

struct cmp //按任务到达CPU的顺序进行存储
{
    bool operator()(const Process &t1,const Process &t2)
    {
        if(t1.arr!=t2.arr)return t1.arr>t2.arr; //arr小的放在上面。小顶堆
        return t1.prior<t2.prior;   //对于同时到达的,prior大的放在上面。大顶堆
    }
};
struct cmp2//按任务执行的顺序存储
{
    bool operator()(const Process &t1,const Process &t2)
    {
        if(t1.prior!=t2.prior)return t1.prior<t2.prior;
        return t1.arr>t2.arr; //prior相同时,arr小的放在上面。即遵循first arrive,first serve

    }
};
int main()
{
    int num;
    int cases=0;
    while(cin>>num)
    {
        Process temp;
        Process temp2;
        if(cases!=0)printf("\n");
        priority_queue<Process,vector<Process>,cmp> Q;   //所有待办任务的队列
        priority_queue<Process,vector<Process>,cmp2> ing; //所有等待中的任务的队列,prior大的放上面
        for(int i=0; i<num; i++)
        {
            cin>>temp.id>>temp.arr>>temp.last>>temp.prior;
            Q.push(temp);
        }
        printf("CASE #%d\n",++cases);
        int timer=0;
        temp=Q.top();
        Q.pop();

        ing.push(temp); //第一个任务进入ing队
        timer=temp.arr; //记录当前时间
        while(1) //注意结束条件不能是Q为空。Q空了之后,还要再运行一次。
        {
            //temp=ing.top();
            if(!Q.empty())
            {
                temp2=Q.top();
                Q.pop();
            }
            else
            {
                temp2.arr=INF; //永远不会到来
                temp2.last=0;
                temp2.prior=0;
                temp2.id=0;
            }
            bool flag=0;
            while(!ing.empty())
            {
                temp=ing.top();
                if(timer+temp.last<=temp2.arr)
                {
                    timer+=temp.last;
                    printf("%d %d\n",temp.id,timer);
                    ing.pop();
                }
                else
                {
                    flag=1;
                    break;
                }
            }
            if(temp2.arr==INF)      //Q空了后,再循环一次,在这儿终止。
            {
                break;
            }
            if(flag)   //如果被打断
            {
                //   temp.arr=timer;
                temp.last=temp.last-(temp2.arr-timer);//更新这个任务还需要的时间
                timer=temp2.arr;
                ing.pop();
                ing.push(temp); //更新ing最上面那个
                ing.push(temp2);
            }
            else if(!Q.empty())//没被打断,说明些时ing队列空了
            {
                timer=temp2.arr;
                ing.push(temp2);
            }
        }

    }
    return 0;
}

解题参考:http://blog.csdn.net/zhuang19922011/article/details/7926063