首页 > 试题广场 >

Table Tennis (30)

[编程题]Table Tennis (30)
  • 热度指数:3873 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
A table tennis club has N tables available to the public. The tables are numbered from 1 to N. For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number. If all the tables are occupied, they will have to wait in a queue. It is assumed that every pair of players can play for at most 2 hours.
Your job is to count for everyone in queue their waiting time, and for each table the number of players it has served for the day.
One thing that makes this procedure a bit complicated is that the club reserves some tables for their VIP members. When a VIP table is open, the first VIP pair in the queue will have the priviledge to take it. However, if there is no VIP in the queue, the next pair of players can take it. On the other hand, if when it is the turn of a VIP pair, yet no VIP table is available, they can be assigned as any ordinary players.

输入描述:
Each input file contains one test case. For each case, the first line contains an integer N (<=10000) - the total number of pairs of players.  Then N lines follow, each contains 2 times and a VIP tag: HH:MM:SS - the arriving time, P - the playing time in minutes of a pair of players, and tag - which is 1 if they hold a VIP card, or 0 if not.  It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open.  It is assumed that no two customers arrives at the same time.  Following the players' info, there are 2 positive integers: K (<=100) - the number of tables, and M (< K) - the number of VIP tables.  The last line contains M table numbers.


输出描述:
For each test case, first print the arriving time, serving time and the waiting time for each pair of players in the format shown by the sample.  Then print in a line the number of players served by each table.  Notice that the output must be listed in chronological order of the serving time.  The waiting time must be rounded up to an integer minute(s).  If one cannot get a table before the closing time, their information must NOT be printed.
示例1

输入

9<br/>20:52:00 10 0<br/>08:00:00 20 0<br/>08:02:00 30 0<br/>20:51:00 10 0<br/>08:10:00 5 0<br/>08:12:00 10 1<br/>20:50:00 10 0<br/>08:01:30 15 1<br/>20:53:00 10 1<br/>3 1<br/>2

输出

08:00:00 08:00:00 0<br/>08:01:30 08:01:30 0<br/>08:02:00 08:02:00 0<br/>08:12:00 08:16:30 5<br/>08:10:00 08:20:00 10<br/>20:50:00 20:50:00 0<br/>20:51:00 20:51:00 0<br/>20:52:00 20:52:00 0<br/>3 3 2
思路见注释。
有一次没过是因为输出时,按照被服务的时间点排序时,如果时间点相等,服务时间长的先输出。
#include<cstdio>
#include<vector>
#include<algorithm>
#include<string.h>
#include<cmath>
using namespace std;
int open=28800,close=75600;
int table[110]={0},tab[110]={0},serve[110]={0};//分别表示每张桌子是否为vip桌子,空闲时间,服务数量
const int maxn=10010;
struct Peo{
    int arrive;
    int stay;
    int vip;
    int sertime;
}peo[maxn];

bool cmp(Peo p1,Peo p2){
    return p1.arrive<p2.arrive;
}
bool cmp2(Peo p1,Peo p2){
    if(p1.sertime==p2.sertime)return p1.arrive>p2.arrive;
    return p1.sertime<p2.sertime;
}
int main(){
    int n,k,m;
    scanf("%d",&n);
    int vis[n];
    memset(vis,0,sizeof(vis));
    for(int i=0;i<n;i++){
        int h,m,s;
        scanf("%d:%d:%d %d %d",&h,&m,&s,&peo[i].stay,&peo[i].vip);
        peo[i].arrive=h*3600+m*60+s;
        if(peo[i].stay>120)peo[i].stay=120;
    }
    scanf("%d %d",&k,&m);
    fill(tab,tab+k,open);//所有桌子的最早服务时间都设置为早上八点
    while(m--){
        int idx;
        scanf("%d",&idx);
        table[idx-1]=1;
    }
    sort(peo,peo+n,cmp);
    int i=0;
    while(i<n){
        if(vis[i]){
            i++;
            continue;
        }
        int aimt=tab[0];//有桌子可用的最早时间
        int aimi=0;//目标桌子编号
        int aimp=i;//目标客户编号
        for(int j=0;j<k;j++){
            if(tab[j]<=peo[i].arrive){//用户,有空桌,不需要等,目标暂定为第一张空桌
                aimi=j;
                aimt=peo[i].arrive;//注意,这里的话最早服务时间是该用户到达的时间
                if(peo[i].vip){//如果是vip用户,还要看看有没有空的vip桌子
                    for(int jj=j;jj<k;jj++){
                        if(table[jj]&&tab[jj]<=peo[i].arrive){
                            aimi=jj;
                            break;
                        }
                    }
                }
                break;
            }
            if(tab[j]<aimt){//没有空桌时先找结束的最早的一张桌子
                aimt=tab[j];
                aimi=j;
            }

        }
        if(!peo[i].vip&&table[aimi]){//如果被普通用户暂定的这张桌子是vip桌子,就去找有没有vip也在等
            for(int ii=i+1;ii<n;ii++){
                if(peo[ii].arrive<=aimt&&peo[ii].vip&&!vis[ii]){//有在等的vip
                    aimp=ii;//vip插队先服务
                    if(peo[ii].arrive>aimt)aimt=peo[ii].arrive;
                    break;
                }
            }
        }
        if(aimt<close){
            serve[aimi]++;
            tab[aimi]=aimt+peo[aimp].stay*60;
        }
        vis[aimp]=1;
        peo[aimp].sertime=aimt;
        if(aimp==i)i++;//如果服务的不是当前查看的这个人,下次还从这个人开始查看
    }
    sort(peo,peo+n,cmp2);
    for(int i=0;i<n;i++){
        if(peo[i].sertime>=close)continue;
        printf("%02d:%02d:%02d ",peo[i].arrive/3600,peo[i].arrive%3600/60,peo[i].arrive%60);
        printf("%02d:%02d:%02d ",peo[i].sertime/3600,peo[i].sertime%3600/60,peo[i].sertime%60);
        printf("%.0f\n",round((peo[i].sertime-peo[i].arrive)/60.0));
    }
    for(int i=0;i<k;i++){
        printf("%d",serve[i]);
        if(i!=k-1)printf(" ");
    }
    return 0;
}


发表于 2019-08-08 09:27:35 回复(1)
这个题目有个坑,当有两张空桌子,1号普通桌,2号VIP桌的时候,来了一个VIP,应该给他2号桌才能AC,这个要求我是没有在题目当中找到的
发表于 2018-09-07 18:11:58 回复(5)

题目要求对乒乓球厅的事件进行模拟。

根据用户到达时间排队,有空桌子则按先到先服务的原则处理,如果队列中有VIP用户并且有VIP桌子空闲,则VIP可以“自成一队”,按照到达顺序直接分配到VIP桌,如果没有VIP桌空闲,则VIP和普通用户同样对待。如果队中没有VIP并且编号最小的恰是VIP桌,普通用户也可以使用VIP桌。

这类题目需要处理桌子的空闲与用户的到达、服务时间之间的关系,需要有一个较好的思路,否则很容易混乱。

一个比较好的思路是为每个桌子设定空闲时间,首先全部初始化为上午8:00,当处理一个人时,首先从桌子列表最前面取到桌子,然后根据自己的到达时间和桌子的空闲时间即可计算出桌子的新空闲时间、用户的等待时间和服务时间(有可能到关门时达不到预期服务时间)。

这道题麻烦在VIP上,如果有VIP用户,他们可以“插队”,要处理这些用户,就会让问题变得复杂,不能简单的取出第一个未服务用户和第一个桌子,而是要考虑有VIP用户和VIP桌子的情况,这里有两种优秀的解法:

①类似归并排序的思想,维护普通用户和VIP用户两个队列。

②仅使用一个队列,先考虑VIP情况,没有VIP被处理则按照正常情况处理,算法来自sunbaigui

我完整的参考了sunbaigui的解法,他的解法非常巧妙,下面罗列一下关键点:

①对用户排序后从前到后处理,初始化服务开始时间为INF,这样当处理完一个人时,他的服务时间不再是INF,由此判断是否处理完毕,不必另设标志。

②不对桌子排序,而是找到所有桌子中空闲时间最早的,从桌子列表从前到后筛选,这样就保证了按照编号的顺序,十分巧妙。

③根据②中找到的最早空闲时间,找出所有符合的桌子和用户,分别存储一个新的容器,后面就针对这两个新的容器处理。

④分情况讨论,单人单桌、多人单桌、多人多桌,在这三种情况下分别判断是否有VIP被服务。

⑤如果④中没有VIP被服务,则取出新容器中第一个用户和第一个桌子,正常处理。

下面的代码来自sunbaigui,我在他代码的基础上加了些注释,方便理解。
package go.jacob.day1024;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Scanner;

public class Demo1 {
    static List<Node> user;
    static List<Table> table;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        user = new ArrayList<Node>();
        table = new ArrayList<Table>();
        // 读入运动员信息
        for (int i = 0; i < n; i++) {
            String[] times = sc.next().split(":");
            Node node = new Node(calTime(times), sc.nextInt()*60, sc.nextInt());
            user.add(node);
        }
        // 读取桌子信息
        int k = sc.nextInt(), m = sc.nextInt();// 桌子数和vip桌子数
        for (int i = 0; i < k; i++) {
            Table t = new Table(0, 8 * 3600, 0);
            table.add(t);
        }
        // 设置vip桌子
        for (int i = 0; i < m; i++) {
            int c = sc.nextInt() - 1;// 桌子的序号为N-1
            table.get(c).tag = 1;
        }
        // 按到时间升序排序
        Collections.sort(user, new Comparator<Node>() {
            @Override
            public int compare(Node n1, Node n2) {
                return n1.arrive - n2.arrive;
            }
        });
//        System.out.println("第一次排序:"+user);
//        System.out.println("第一次排序:"+table);
        // 开始处理服务
        for (int i = 0; i < n; i++) {
            if (user.get(i).serve != Integer.MAX_VALUE)
                continue;
            // 找出最早空闲的时间,采用从头到尾遍历的方式。
            int minFreeTime = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                minFreeTime = Math.min(minFreeTime, table.get(j).freeTime);
            }
            // 确定最早开始服务的时间
            int timePoint = Math.max(user.get(i).arrive, minFreeTime);
            if (timePoint >= 21 * 3600)
                break;// 超时,退出循环
            List<Integer> userList = new ArrayList<Integer>();
            List<Integer> tableList = new ArrayList<Integer>();
            // 根据time Point找到所有可能被服务的人,是为了处理有VIP优先去VIP桌的情况
            for (int j = i; j < n; j++)
                if (user.get(j).serve == Integer.MAX_VALUE && user.get(j).arrive <= timePoint)
                    userList.add(j);
            // 找出timePoint之前空闲的桌子,因为可能用户到达比较晚,会有多个桌子空闲
            for (int j = 0; j < k; j++)
                if (table.get(j).freeTime <= timePoint)
                    tableList.add(j);

            boolean flag = false;// 判断是否处理了一个服务
            // 首先特殊处理VIP,如果没有VIP被处理则处理一个普通用户,每次只处理一个
            if (userList.size() == 1 && tableList.size() > 1) {
                if (user.get(userList.get(0)).tag == 1) {
                    for (int j = 0; j < tableList.size(); j++) {
                        if (table.get(tableList.get(j)).tag == 1) {
                            flag = true;
                            updateInfo(userList.get(0), tableList.get(j));
                            break;
                        }
                    }
                }
            } else if (tableList.size() == 1 && userList.size() > 1) {// 一桌多人,要考虑VIP用户
                if (table.get(tableList.get(0)).tag == 1) {
                    for (int j = 0; j < userList.size(); j++) {
                        if (user.get(userList.get(j)).tag == 1) {
                            flag = true;
                            updateInfo(userList.get(j), tableList.get(0));
                            break;
                        }
                    }
                }
            } else if (tableList.size() > 1 && userList.size() > 1) {// 多人多桌
                for (int j = 0; j < tableList.size(); j++) {
                    if (table.get(tableList.get(j)).tag == 1) {
                        for (int u = 0; u < userList.size(); u++) {
                            if (user.get(userList.get(u)).tag == 1) {
                                flag = true;
                                updateInfo(userList.get(u), tableList.get(j));
                                break;
                            }
                        }
                    }
                }
            }
            if (!flag)// 如果还没有被处理,则第一个与第一个配对
                updateInfo(userList.get(0), tableList.get(0));
            i--;// 如果处理的是第i个人,写一次循环会直接continue
        }
        // 输出处理
        // 根据服务时间和到达时间排序
        Collections.sort(user, new Comparator<Node>() {
            @Override
            public int compare(Node o1, Node o2) {
                if (o1.serve == o2.serve)
                    return o2.arrive - o1.arrive;
                return o1.serve - o2.serve;
            }
        });
        for (int i = 0; i < n; i++) {
            if (user.get(i).serve >= 21 * 3600)
                break;
            int h1, m1, s1, h2, m2, s2;
            int t = user.get(i).arrive;
            h1 = t / 3600;
            t %= 3600;
            m1 = t / 60;
            t %= 60;
            s1 = t;
            t = user.get(i).serve;
            h2 = t / 3600;
            t %= 3600;
            m2 = t / 60;
            t %= 60;
            s2 = t;
            // 等待时间四舍五入
            System.out.printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", h1, m1, s1, h2, m2, s2,
                    (user.get(i).wait + 30) / 60);
        }
        for (int i = 0; i < k; i++) {
            if (i != k - 1)
                System.out.printf("%d ", table.get(i).num);
            else
                System.out.printf("%d", table.get(i).num);
        }
    }

    // 更新信息
    private static void updateInfo(Integer userID, Integer tableID) {
        
        user.get(userID).serve = Math.max(user.get(userID).arrive, table.get(tableID).freeTime);

        user.get(userID).wait = user.get(userID).serve - user.get(userID).arrive;
        table.get(tableID).num++;
        table.get(tableID).freeTime = user.get(userID).serve + Math.min(user.get(userID).process, 2 * 3600);
//        System.out.println("hhhhhhhhh:"+table.get(tableID));
    }

    // 计算时间,以秒为单位
    private static int calTime(String[] times) {
        int h = Integer.parseInt(times[0]);
        int m = Integer.parseInt(times[1]);
        int s = Integer.parseInt(times[2]);

        return h * 3600 + m * 60 + s;
    }
}

/*
 * 运动员类
 */
class Node {
    int arrive, process, tag;// 到达时间、打球时间和VIP标志
    int serve = Integer.MAX_VALUE;
    int wait = Integer.MAX_VALUE;// 服务开始时间和等待时间

    public Node(int arrive, int process, int tag) {
        super();
        this.arrive = arrive;
        this.process = process;
        this.tag = tag;
    }

    @Override
    public String toString() {
        return "Node [arrive=" + arrive + ", process=" + process + ", tag=" + tag + ", serve=" + serve + ", wait="
                + wait + "]";
    }
}

class Table {
    int tag;// vip标志
    int freeTime, num;// 空闲时间和服务数

    public Table(int tag, int freeTime, int num) {
        super();
        this.tag = tag;
        this.freeTime = freeTime;
        this.num = num;
    }

    @Override
    public String toString() {
        return "Table [tag=" + tag + ", freeTime=" + freeTime + ", num=" + num + "]";
    }
    
}

发表于 2017-10-25 10:58:56 回复(1)
易错点:
1.当有vip玩家在等待且有空闲vip球桌时,无论编号是大是小,都应该先将vip球桌分配给vip玩家。(题目没明确说明)
2.当玩家打球时间超过2小时,应予以纠正。(一个难找的bug)
#define lastSecond 75600
using namespace std;
//时间字符串转整数第几秒
int timeToInt(string time){
	int h, m, s;
	sscanf(time.c_str(), "%d:%d:%d", &h, &m, &s);
	int res = (h * 3600 + m * 60 + s);
	return res > lastSecond ? lastSecond : res;	//最晚21:00离开
}
struct Player {
	int arrive;
	int server;
	int leaf;
	int play;
	int tableId;
	bool isVip;
	void init(string time, int wait, bool vip){
		this->arrive = timeToInt(time);
		this->server = wait;
		this->isVip = vip;
	}
	void printMsg(){
		printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",
			arrive / 3600, (arrive % 3600) / 60, arrive % 60,
			play / 3600, (play % 3600) / 60, play % 60,
			(play - arrive) / 60 + ((play - arrive) % 60 >= 30 ? 1 : 0));
	}
	void sit(int time, int table){
		play = time;
		leaf = (time + server * 60);
		leaf = leaf> lastSecond ? lastSecond : leaf;
		tableId = table;
		return;
	}
};
//先到的玩家先出
bool compare(const Player &a, const Player &b){
	return a.arrive < b.arrive;
}

struct Table{
	int index;
	int times;
	bool isVip;
};

//vip 或 序号小的球桌先出列
struct order2 {
	bool operator()(const Table&a, const Table &b){
		return a.index <= b.index;
	}
};
//离开时间早的先出列
struct order3 {
	bool operator()(const Player&a, const Player &b){
		return a.leaf > b.leaf;
	}
};

vector<Player> pQueat;
vector<Player*> vipQueat;
vector<Table> tQueat;
set<Table, order2> tableState;	//空闲的球桌
priority_queue<Player, vector<Player>,order3> playing;		//正在玩的玩家

int tablesNum, playerNumber, vipNumber;
int main(){
	//获取玩家数据
	scanf("%d", &playerNumber);
	pQueat.resize(playerNumber);
	for (int i = 0; i < playerNumber; i++) {
		string time;
		int stay, tag;
		cin >> time >> stay >> tag;
		pQueat[i].init(time, stay>120?120:stay, tag==1?true:false);
	}
	//获取球桌数据
	scanf("%d %d", &tablesNum, &vipNumber);
	tQueat.resize(tablesNum);
	for (int i = 0; i < vipNumber; i++){
		int vipIndex;
		scanf("%d", &vipIndex);
		tQueat[vipIndex - 1].isVip = true;
	}
	//球桌开始就绪
	for (int i = 0; i < tablesNum; i++){
		tQueat[i].index = i;
		tableState.insert(tQueat[i]);
	}
	//玩家按照到达时间排序
	sort(pQueat.begin(), pQueat.begin()+playerNumber, compare);
	//记录队列中vip玩家的位置
	for (unsigned int i = 0; i < pQueat.size(); i++){
		if (pQueat[i].isVip){
			vipQueat.push_back(&pQueat[i]);
		}
	}
	int fvip = 0, fplayer = 0;	//第一个vip和普通玩家的位置
	//模拟一天的二十四小时
	for (int i = 0; i <= lastSecond; i++){
		//若有玩家结束,则返还座位
		while (true){
			if (playing.empty()) break;
			Player tmp = playing.top();
			if (tmp.leaf > i) break;
			tableState.insert(tQueat[tmp.tableId]);
			playing.pop();
		}
		//若有空位则分配给等待的玩家
		if (i == lastSecond) break;
		while (true){
			if (tableState.empty()) break;
			while (fplayer  < pQueat.size() && pQueat[fplayer].arrive < 0) fplayer++;
			while (fvip  < vipQueat.size() && vipQueat[fvip]->arrive < 0) fvip++;
			if (fplayer >= pQueat.size() ) break;
			if (pQueat[fplayer].arrive > i) break;
			//若队列中有vip玩家且有空闲vip桌子,则vip玩家先入座
			if (fvip < vipQueat.size() && vipQueat[fvip]->arrive > 0 && vipQueat[fvip]->arrive <= i){
				set<Table>::iterator it;
				for (it = tableState.begin(); it != tableState.end() && !it->isVip; it++);
				if (it != tableState.end()){
					Table table1 = *it;
					tableState.erase(it);
					Player player1 = *vipQueat[fvip];
					player1.sit(i, table1.index);
					playing.push(player1);
					player1.printMsg();
					vipQueat[fvip]->arrive = -1;
					tQueat[table1.index].times++;
					continue;
				}
			}
			//其余情况下,所有桌子一视同仁
			Player player1 = pQueat[fplayer];
			Table table1 = *tableState.begin();
			tableState.erase(tableState.begin());
			player1.sit(i, table1.index);
			playing.push(player1);
			player1.printMsg();
			pQueat[fplayer].arrive = -1;
			tQueat[table1.index].times++;
		}
	}
	//打印桌子使用次数
	for (int i = 0; i < tQueat.size(); i++){
		printf("%d%s", tQueat[i].times, i == tQueat.size() - 1 ? "\n" : " ");
	}
	return 0;
}


编辑于 2020-02-24 11:46:43 回复(1)
#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct people{
	int arrivetime;
	int endtime;
	int tag;
	int process;
	int resttime;
	bool operator<(people & it){
		return arrivetime<it.arrivetime;
	}
};
//que等待队列,wind乒乓球桌,windvip是否为vip桌,serve记录每桌服务人数,servetime记录服务顺序
vector<int> que,wind,windvip,serve,servetime;
//v记录了顾客的信息,按到达时间序排列,在服务过程中用v的序号代替某个人
vector<people> v;
//now当前时间 ,num客户人数,win窗口(球桌)数,vip顾客的vip数
int now=8*3600;
int num;
int win;
int vip;
bool find();
bool windisnfull();
int Min();
bool windisempty();
void dowork();
string tostring(int);
//银行排队模型
int main(){
	cin>>num;
	v.resize(num);
	for(int i=0;i<num;i++){
		int hh,mm,ss;
		scanf("%d:%d:%d",&hh,&mm,&ss);
		v[i].arrivetime=hh*3600+mm*60+ss;
		cin>>v[i].process>>v[i].tag;
		v[i].process*=60;
		//这里是坑点,每个人使用时间不得超过两个小时
		v[i].process=min(v[i].process,7200);
		v[i].resttime=v[i].process;
		que.push_back(i);
	}
	cin>>win>>vip;
	serve.resize(win,0);
	wind.resize(win,-1);
	windvip.resize(win,0);
	for(int i=0;i<vip;i++){
		int j=0;
		cin>>j;
		windvip[j-1]=1;
	}
	sort(v.begin(),v.end());
	//一准备,一情况,两过程
	//当还有人时继续处理
	while(!windisempty() || !que.empty()){
		//当前台有空位时,一直加符合条件的人进入
		while(windisnfull())
			//如果无人满足条件,find返回0,不再加人,添加顾客成功返回1
			if(!find())
				break;
		//如果前台空且下一个顾客还未到时,时间空转
		if(windisempty() && !find()){
			now=v[que.front()].arrivetime;
			continue;
		}
		//处理用户业务或者等一个人进来,做哪个操作取决于哪个时间短
		//如果前台有空位且下一个客户到达时间比最快服务完成时间还短,时间跳至下个顾客的到达时间,前台所有人剩余时间减少
		if(windisnfull() && !que.empty() && v[que.front()].arrivetime-now < Min()){
			for(int j=0;j<win;j++)
				if(wind[j]!=-1)
					v[wind[j]].resttime-=(v[que.front()].arrivetime-now);
			now = v[que.front()].arrivetime;
			continue;
		}
		//否则直接处理一个客户
		dowork();
	}
	for(int i=0;i<num;i++)
		//如果顾客的服务开始时间超过了营业时间,不打印,否则打印
		//注意等待时间单位是分钟,30秒四舍五入,打印顺序是顾客参与服务的时间
		if(v[servetime[i]].endtime-v[servetime[i]].process<21*3600)
			cout<<tostring(v[servetime[i]].arrivetime)<<" "<<tostring(v[servetime[i]].endtime-v[servetime[i]].process)<<" "<<(v[servetime[i]].endtime-v[servetime[i]].arrivetime-v[servetime[i]].process+30)/60<<endl;
	for(int i=0;i<win;i++){
		if(i!=0)cout<<" ";
		cout<<serve[i];
	}
	return 0;
}
//find函数检查能否从队列中选出顾客进行服务,如果无人满足条件,返回false,否则添加一个人到服务队列,返回true
bool find(){
	if(que.empty() || v[que.front()].arrivetime>now)return false;
	//找一个空的服务位置
	//先找有没有vip服务位置空出来,如果有vip桌子,先为vip桌子找vip顾客
	int i=0;
	for(i=0;i<win;i++)
		if(windvip[i]==1 && wind[i]==-1)
			//找有没有vip人可以进,没有的话加入普通顾客
			for(vector<int>::iterator it=que.begin();it<que.end();it++)
				if(v[*it].tag==1 && v[*it].arrivetime<=now){
					wind[i]=*it;
					servetime.push_back(*it);
					que.erase(it);
					return true;
				}
	//添加vip失败,从序号最小的桌子开始添加第一个等待的顾客
	for(i=0;i<win;i++)
		if(wind[i]==-1){
			wind[i]=que.front();
			servetime.push_back(que.front());
			que.erase(que.begin());
			return true;
		}
	return true;
};
bool windisnfull(){
	for(int i=0;i<win;i++)
		if(wind[i]==-1)
			return true;
	return false;
};
//正在接受服务顾客们的最短完成时间
int Min(){
	int min=100000;
	for(int i=0;i<win;i++)
		if(wind[i]!=-1)
			if(v[wind[i]].resttime<min)
				min=v[wind[i]].resttime;
	return min;
};
//前台所有人的剩余服务时间减少,时间经过,剩余时间为0的顾客出队
void dowork(){
	int a;
	int t=Min();
	//所有前台时间减少,时间经过
	for(int i=0;i<win;i++)
		if(wind[i]!=-1)
			v[wind[i]].resttime-=t;
	now+=t;
	for(int i=0;i<win;i++)
		if(wind[i]!=-1)
			if(v[wind[i]].resttime==0){
				v[wind[i]].endtime=now;
				if(now-v[wind[i]].process<21*3600)
					serve[i]++;
				wind[i]=-1;
			}
};
bool windisempty(){
	for(int i=0;i<win;i++)
		if(wind[i]!=-1)
			return false;
	return true;
};
string tostring(int time){
	int hh=time/3600;
	int mm=time%3600/60;
	int ss=time%60;
	char c[9];
	c[0]=hh/10+'0';
	c[1]=hh%10+'0';
	c[2]=':';
	c[3]=mm/10+'0';
	c[4]=mm%10+'0';
	c[5]=':';
	c[6]=ss/10+'0';
	c[7]=ss%10+'0';
	c[8]='\0';
	string s(c);
	return s;
}
由于编译器不同,pat官网的g++可以过,clang++通不过编译,提供一种比较通用的银行业务过程模型,

主要思想是站在时间的角度来处理事件,需要一个等待队列,一个服务区(一般是一维vector,根据情况可能也会用vector<vector>),一个顾客信息记录表(包括到达时间,服务开始时间,服务时长,服务剩余时间,服务结束时间),
开始的时候所有顾客按到达时间序全部进入队列,当前时间设置为营业开始时间,一个循环包括4个过程

每一次循环都触发了一个时间事件,now经过了一段时间
while(等待队列或者服务队列还有人){

        1)准备工作
        在这个时间点上,将所有能添加进服务队列的人添加进去

        2)如果这个时候没有顾客到达,同时前台也没有人在接受服务,那么时间就白白流过,直至等到顾客
       if(下一个顾客未到 && 前台空)
         时间白白流过,跳转到下一个顾客到达的时间点,continue

        3)这个时间事件可能有两种情况,分别是完成了一次服务时间段,或者是在服务期间又加入了一个顾客,取决于哪个时间事件短,这种情况其实可以归并到第二种情况,但是在具体题目条件和要求不同的时候,不要杂糅起来考虑,因为这种情况前台是在工作的,剩余时间要减少
        if(前台有空位 && 顾客到来时间<最快服务完成时间)
        时间流过,跳转到下一个顾客到达的时间点,前台所有顾客剩余服务时间减少,continue

        4)剩下的情况就是直接服务到第一个顾客完成的时间,这个时候所有顾客的剩余服务时间减少,要记录完成时间,
        时间流过,跳转到第一个顾客服务完毕的时间,前台所有顾客剩余时间减少,所有剩余时间为0的顾客出列,记录服务结束时间,相应服务台置空
}

具体问题只需要想清楚在哪里设置条件即可,比如顾客比关门时间晚到,仍然可以不改结构,只在打印的时候判断v[i].endtime-v[i].process即可推出开始服务时间是否非法,祝各位考出好成绩,也欢迎一起交流
发表于 2017-02-16 23:48:25 回复(0)
恶心的题目,给爷爪巴,本来PAT已经过了,牛客用例10改过之后才过没过。前面人没说清楚,这个用例最坑的地方在于按照被服务的时间点排序时,如果服务开始的时间点相等,是vip的先输出,如果都是vip,那么先到的先输出。
	#include <iostream>
	#include <string>
	#include <vector>
	#include <algorithm>
	#include <functional>
	#include <cmath>

	using namespace std;
	const int CLOSE_AT = 21 * 3600;
	class Customer
	{
	public:
		Customer(int &_arriveAt, int &_howLong, bool _isVip = false)
		{
			arriveAt = _arriveAt;
			howLong = _howLong;
			isVip = _isVip;
		}
		int arriveAt;
		int howLong;
		bool isVip;
		int start = CLOSE_AT;
	};

	class Table
	{
	public:
		Table(int _nextTime = 3600 * 8, bool _isVip = false)
		{
			nextTime = _nextTime;
			isVip = _isVip;
		}
		int nextTime;
		bool isVip;
		int serveCount = 0;
	};

	

	int main()
	{

		int n;
		int arriveAt;
		int isVip;
		int h, m, s;
		int tableCount, vipTableCount;
		vector<Customer> customers;
		vector<Table> tables;
		int vipIdx = -1;
		int idx = 0;
		function<void()> getVipIdx = [&]()
		{	
			vipIdx++;
			while(vipIdx < customers.size() && customers[vipIdx].isVip == 0){
				vipIdx++;
			}
		};

		function<int()> getTable = [&]()
		{
			int min = CLOSE_AT;
			int res = -1;
			for (int i = 0; i < tables.size(); i++)
			{
				if(tables[i].nextTime <= customers[idx].arriveAt){
					return i;
				}
				if (tables[i].nextTime < min)
				{
					min = tables[i].nextTime;
					res = i;
				}
			}
			return res;
		};

		function<int()> getVipTable = [&]()
		{
			int min = CLOSE_AT;
			int res = -1;
			for (int i = 0; i < tables.size(); i++)
			{
				if(	tables[i].isVip){
					if(tables[i].nextTime <= customers[idx].arriveAt){
						return i;
					}
					if (tables[i].nextTime < min){
						min = tables[i].nextTime;
						res = i;
					}
				}
				
			}
			return res;
		};

		function<void(int, int)>  alloctable = [&](int personid, int tableid) {
			if(customers[personid].arriveAt <= tables[tableid].nextTime)
				customers[personid].start = tables[tableid].nextTime;
			else
				customers[personid].start = customers[personid].arriveAt;
			
			tables[tableid].nextTime = customers[personid].start + customers[personid].howLong * 60;
			tables[tableid].serveCount++;
		};
		
		cin >> n;
		for (int i = 0; i < n; i++)
		{
			int howLong;
			scanf("%d:%d:%d %d %d", &h, &m, &s, &howLong, &isVip); //tactfully handle the string-form time for calculation
			arriveAt = h * 3600 + m * 60 + s;
			if (arriveAt < CLOSE_AT)
			{
				if(howLong > 120){
					howLong = 120;
				}
				customers.emplace_back(arriveAt, howLong, isVip == 1?true:false);
			}
		}

		cin >> tableCount >> vipTableCount;
		tables.resize(tableCount);
		int vipTableNo;
		for (int i = 0; i < vipTableCount; i++){
			cin >> vipTableNo;
			tables[vipTableNo - 1].isVip = true;
		}
		sort(customers.begin(), customers.end(), [](Customer a, Customer b)
			{ return a.arriveAt < b.arriveAt; });
		getVipIdx();
		// 分4种情况讨论
		while (idx < customers.size())
		{
			int nextTable = getTable();
			if(nextTable == -1){
				break;
			}
			if(customers[idx].isVip && idx < vipIdx){
				idx++;
				continue;
			}
			if (tables[nextTable].isVip)
			{ //next table is VipTable

				if (customers[idx].isVip)
				{
					alloctable(idx, nextTable);
					if(idx == vipIdx){
						getVipIdx();
					}
					idx++;
				}
				else
				{ //first customer not vip
					if (vipIdx < customers.size() && customers[vipIdx].arriveAt <= tables[nextTable].nextTime)
					{ //vip jump in
						alloctable(vipIdx, nextTable);
						getVipIdx();
					}
					else
					{ //arrange first common
						alloctable(idx, nextTable);
						idx++;
					}
				}
			}
			else
			{ //next table not vipTable


				// any vip in the row wating? if so, need to know if any vipTable free at the same time with bigger idx
				if(!customers[idx].isVip){
					alloctable(idx, nextTable);
					idx++;
				}
				else
				{
					int nextVipTable = getVipTable();
					if (nextVipTable != -1 && customers[vipIdx].arriveAt >= tables[nextVipTable].nextTime)
					{ //vip jump in
						alloctable(vipIdx, nextVipTable);
						if(vipIdx == idx){
							getVipIdx();
						}
						idx++;
					}
					else
					{
						alloctable(idx, nextTable);
						if(vipIdx == idx){
							getVipIdx();
						}
						idx++;
					}
				}
			}
		}
		sort(customers.begin(), customers.end(), [](Customer a, Customer b){
			if(a.start != b.start){
				return a.start < b.start;
			}else if(a.isVip != b.isVip){
				return (int)a.isVip > (int)b.isVip;
			}else{
				return a.arriveAt < b.arriveAt;
			}
		});
		for(int i = 0; i < customers.size() && customers[i].start < CLOSE_AT; i++){
			printf("%02d:%02d:%02d ", customers[i].arriveAt / 3600, customers[i].arriveAt % 3600 / 60, customers[i].arriveAt % 60);
			printf("%02d:%02d:%02d ", customers[i].start / 3600, customers[i].start % 3600 / 60, customers[i].start % 60);
			printf("%.0f\n", round((customers[i].start - customers[i].arriveAt) / 60.0));
		}
		for(int i = 0; i < tables.size(); i++) {
			if(i != 0) printf(" ");
			printf("%d", tables[i].serveCount);
		}
		
		return 0;
	}


发表于 2021-07-29 20:25:23 回复(0)
本题是一道模拟题,我们一般两种思路,一种是以玩家视角处理,另一种是用时间视角处理,因为题目中vip的设定,所以从玩家视角稍微繁琐一些,我们就用时间视角模拟每秒钟的事件就行了。

对于每一个时刻:
首先清空桌子上该时刻需要走的玩家;
然后把该时刻来的玩家放在两个排队序列里;
根据空余桌子的情况处理玩家{
    我们首先处理vip桌子存在且有vip玩家排队情况,此时刻按照题意"For any pair of players, if there are some tables open when they arrive, they will be assigned to the available table with the smallest number.",所以一定先安排vip玩家选择最小vip桌子。
    上一步操作完成后,此时一定不会同时存在vip桌子和vip玩家;那么所有的对象一视同仁,都做普通处理就好了。
}
细节点:
最后的时刻21:00:00是不能进场的;
时间四舍五入的处理
21点和之后进场的人不能打印,所以我用ans数组保存每个安排玩家序号,最后打印ans结果
#include <cstdio>
#include <algorithm>
#include <queue>
using namespace std;

const int MAX_N = 10001, MAX_K = 101;
queue<int> qv, qo;
int ans[MAX_N], nums = 0;

int getTime(int h, int m, int s) { return h*3600 + m*60 + s;}

const int BEGIN = getTime(8, 0, 0), END = getTime(21, 0, 0), MAX_PLAY = getTime(2, 0, 0);

void prinTime(int t) { printf("%02d:%02d:%02d ", t/3600, t%3600/60, t%60);}

struct Player {
    int arrTime, serTime = -1, playTime, leaveTime;
    bool isVip;
    Player(int a = -1, int p = -1, bool t = false) : arrTime(a), playTime(p), isVip(t) {}
}players[MAX_N];

struct Table {
    int use = -1, count = 0;
    bool isVip = false;
}tables[MAX_K];

bool cmpArrTime(Player a, Player b) { return a.arrTime < b.arrTime;}

void goPlay(int p, int i, int t) {//更新入场后的信息: 玩家p 在i号桌 t时刻入场打球
    ans[nums++] = p;   //ans数组按时间顺序记录每个进场打球的玩家
    tables[i].use = p;
    tables[i].count ++;
    players[p].serTime = t;
    players[p].leaveTime = t + players[p].playTime;
}

int main() {
    int N, K, M;
    int h, m, s, pt, tag, p, cur = 0;

    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        scanf("%d:%d:%d%d%d", &h, &m, &s, &pt, &tag);
        players[i] = Player(getTime(h,m,s), min(MAX_PLAY, getTime(0,pt,0)), tag==1);
    }

    scanf("%d%d", &K, &M);
    for(int i = 0; i < M; ++i) {
        scanf("%d", &tag);
        tables[tag-1].isVip = true;
    }//至此完成所有信息读入

    sort(players, players+N, cmpArrTime);
    for(int t = BEGIN; t < END; ++t) {//时间驱动模拟
        for(int i = 0; i < K; ++i) {//重置球桌,把球桌中此刻要走的玩家清除
            p = tables[i].use;
            if(p >= 0 && players[p].leaveTime == t) tables[i].use = -1;   
        }

        if(cur < N && players[cur].arrTime == t) {//把此刻来的人放进队列
            if(players[cur].isVip) qv.push(cur);
            else qo.push(cur);
            cur++;
        }

        for(int i = 0; i < K; ++i) {// 如果有vip排队,匹配空闲vip桌
            if(qv.empty()) break;
            if(tables[i].isVip && tables[i].use == -1 ) {
                p = qv.front();
                goPlay(p, i, t);
                qv.pop();
            }  
        }
        
        for(int i = 0; i < K; ++i) {// 只要有人排队,我们就把所有对象当普通的处理
            if(qv.empty() && qo.empty()) break;
            if(tables[i].use ==-1) {
                if(qv.empty() || qo.size() && qo.front() < qv.front()) p = qo.front();
                else p = qv.front();////返回队列中最早入队的人p
                goPlay(p, i, t);
                if(qv.size() && p == qv.front()) qv.pop();
                else qo.pop();
            }
        }
    }

    for(int i = 0; i < nums; ++i) {
        p = ans[i];
        prinTime(players[p].arrTime);
        prinTime(players[p].serTime);
        printf("%d\n", (players[p].serTime - players[p].arrTime + 30) / 60);
    }

    for(int i = 0; i < K; ++i) {
        printf("%d",tables[i].count);
        if(i < K-1) printf(" ");
    }
    return 0;
}


编辑于 2021-07-06 16:58:45 回复(0)
感觉好多大神情况分得太细了,我的算法如下,个人认为主程序是比较简洁的:
1. 对时间轴8点-21点的每一秒进行更新,其实才几万秒
2. 每一秒按顺序做三件事:
①请走该走的人
②如果有人arrive,就插入队尾;
③最后对队列进行处理,直到队列空了或者没有桌子可以打为止;每轮处理先找VIP,按有没有VIP分两种情况,这个大家都讨论很多了。

个人经验:
1. 一开始太滥用stl,导致迭代器乱指,总是出错,后来按自己需求写了一个允许中段删除的“链式队列”(严格来说不算队列)完美解决问题(如果不写,直接用stl这段代码会短30多行);把“时间”专门写一个结构体也非常方便
2. 坑: 桌子使用时间超过120分钟要改成120分钟;
3. 人和桌都不需要写结构体,全局数组更高效;排序方面无脑用map与整型id相互映射
#pragma warning (disable:4996)
#include <iostream>
#include <cstring>
#include <map>
using namespace std;

#define MAX 10009

int N, K, M;
typedef struct Time {
    int h, m, s;
    Time() :h(0), m(0), s(0) {}
    Time(int _h, int _m, int _s) :h(_h), m(_m), s(_s) {}
    Time(int sec) :h(sec / 3600), m(sec / 60 % 60), s(sec % 60) {}
    int seconds() const { return h * 3600 + m * 60 + s; }
    bool operator <(const Time& t)const {
        if (h < t.h)return true;
        else if (h == t.h)
            if (m < t.m)return true;
            else if (m == t.m)
                return s < t.s;
        return false;
    }
    void printout() {
        if (h < 10)cout << 0 << h;
        else cout << h; cout << ":";
        if (m < 10)cout << 0 << m;
        else cout << m; cout << ":";
        if (s < 10)cout << 0 << s;
        else cout << s; cout << " ";
    }
}Time;
int wait_mins(const Time& a, const Time& b) {
    int ret = a.seconds() - b.seconds();
    return ret % 60 >= 30 ? ret / 60 + 1 : ret / 60;
}

map<Time, int> at_id; multimap<Time, int> st_id;
Time at[MAX], st[MAX]; int pt[MAX], wt[MAX], is_vip[MAX];//人
int ptable[MAX], ntable[MAX], vtable[MAX];//桌

typedef struct Node { int id; struct Node* next, * prior; }Node;
typedef struct Lqueue {
    Node* header, * trailer;
    Lqueue() {
        header = new Node; trailer = new Node;
        header->next = trailer; trailer->next = NULL;
        trailer->prior = header; header->prior = NULL;
    }
    bool empty() { return header->next == trailer; }
    void push(int e) {
        Node* x = new Node; x->id = e;
        x->next = trailer; x->prior = trailer->prior;
        trailer->prior->next = x; trailer->prior = x;
    }
    int top() { return header->next->id; }
    int pop() {
        if (empty())return 0;
        Node* p = header->next; int ret = p->id;
        header->next = p->next; p->next->prior = header;
        delete p; return ret;
    }
    Node* find_vip() {
        Node* p = header;
        while ((p = p->next) != trailer) if (is_vip[p->id])return p;
        return NULL;
    }
    void remove_vip(Node* p) {
        p->prior->next = p->next; p->next->prior = p->prior;
        //delete p;
    }

}Lqueue;

Lqueue Q;

void push_people(int t) {
    for (int i = 1; i <= K; ++i) {
        int id = ptable[i];
        if (id && t >= st[id].seconds() + pt[id] * 60)ptable[i] = 0;
    }
}

void serve(int i, int id, int t) {
    ptable[i] = id; ++ntable[i];
    st_id.insert(make_pair(Time(t), id)); st[id] = Time(t);
}

bool normal_arrange(int id, int t) {
    if (!id)return false;
    int isFull = true;
    for (int i = 1; i <= K; ++i)
        if (!ptable[i]) { isFull = false; serve(i, id, t); break; }
    return !isFull;
}
bool vip_arrange(int vid, int t) {
    int has_vtable = false;
    for (int i = 1; i <= K; ++i)
        if (!ptable[i] && vtable[i]) {
            has_vtable = true; serve(i, vid, t); return true;
        }
    if (!has_vtable) {
        bool isOK = normal_arrange(Q.top(), t);
        if (isOK)Q.pop(); return isOK;
    }
    return false;
}

int main()
{
    //初始化与输入
    memset(pt, 0, sizeof(pt));
    memset(is_vip, 0, sizeof(is_vip));
    memset(vtable, 0, sizeof(vtable));
    memset(ntable, 0, sizeof(ntable));
    memset(ptable, 0, sizeof(ptable));
    cin >> N; int hh, mm, ss;
    for (int id = 1; id <= N; ++id) {
        scanf("%d:%d:%d", &hh, &mm, &ss);
        at_id[Time(hh, mm, ss)] = id; at[id] = Time(hh, mm, ss);
        cin >> pt[id] >> is_vip[id];
        if (pt[id] > 120)pt[id] = 120;//玩超过2小时要修正
    }
    cin >> K >> M; int tmp;
    for (int i = 1; i <= M; ++i) { cin >> tmp; vtable[tmp] = 1; }

    //模拟
    int open = Time(8, 0, 0).seconds(), close = Time(21, 0, 0).seconds();
    auto it = at_id.begin(); int front_at = it->first.seconds();
    for (int t = open; t < close; ++t) {
        push_people(t);//赶人
        if (t == front_at) {//如果有人来
            Q.push(it->second);
            if (++it != at_id.end())front_at = it->first.seconds();
        }
        bool isOK = true;
        while (!Q.empty() && isOK) {//处理队列,直到无法处理
            Node* v = Q.find_vip();
            if (v) {
                if (isOK = vip_arrange(v->id, t))Q.remove_vip(v);
            }
            else if (isOK = normal_arrange(Q.top(), t))Q.pop();
        }
    }

    //输出
    for (auto ii = st_id.begin(); ii != st_id.end(); ++ii) {
        int id = ii->second;
        at[id].printout(); st[id].printout();
        cout << wait_mins(st[id], at[id]) << endl;
    }
    for (int i = 1; i <= K; ++i) { cout << ntable[i]; if (i < K)cout << " "; }
    return 0;
}


发表于 2021-03-05 06:54:16 回复(0)
//1.这个题和现实生活中感觉有点不一样,现实中,如果一个vip桌子编号比一个普通桌子小,这时来了一个普通客户(后面没有vip客户时),应该首先
//安排为普通桌子,而在本题中是首先安排编号小的桌子。
//2.vip客户只用考虑当前时间的是否还有vip客户在等,不用考虑以后来的vip客户。并且vip客户优先安排vip桌子。
//3.优先级队列有点行不通,因为其出队顺序不好确定,不能以桌子的最早服务时间来出队,比如两个桌子都是8点,一个客人8点到,另一个客人12点到,那么都应该安排到第一张桌子上
//4.这个题其实一想很简单,就按正常的思路来讲,
/*
	第一先确定是否是vip客户,如果是的话首先找vip桌子,如果vip桌子有空闲就安排,没有空闲就记录一个vip桌子里面的最早的服务时间,并且这时候
去普通桌子里面找是否有空闲的,若没有也需记录一个普通桌子里的最早服务时间。如果此时都没有空闲桌子,比较记录的普通桌子和vip桌子谁的最早服务时间更早,
则应该给该vip客户安排这个桌子。
	对于非vip客户,直接去找所有空闲桌子(不区分vip桌和非vip桌,因为普通用户也可以坐vip桌)中编号最小的,若没有空闲桌子,
	则记录一个最早的服务时间桌子,就安排这个桌子给该非vip客户。!!!注意,这里可以不判断,因为题目中说了没有两个客户到达时间相同,因此和当前客户就是最新达到的,
	即使后面有vip客户,那也是后续的安排了,因此他可以直接去用这张vip桌子,(即使前面有vip在等某张桌子,那么这个桌子的最早服务时间也是算上了该vip的laytime的)
    如果题目中有相同达到时间的客户,那么这时候需要判断,如果当前客户是非vip客户并且给他预先安排了vip桌子,那么需要判断,跟这位客户一同达到的是否还有vip客户,如果有vip客户,那么则优先安排给
	该vip客户,本客户留着下一次循环安排(记录下标i,本次下标不加1,设置visit数组将vip设置为已安排,每次循环判断一下即可),这段代码我注释了
       参照了大神的思路和代码
*/
#include<cstdio>
(802)#include<vector>
#include<algorithm>
(831)#include<string.h>
#include<malloc.h>
(756)#include<cmath>
using namespace std;
int open=28800,close=75600;
int table[110]={0},tab[110]={0},serve[110]={0};
//分别表示每张桌子是否为vip桌子,空闲时间,服务数量
const int maxn=10010;
struct Peo{   
	int arrive; 
	int stay; 
	int vip; 
	int sertime;
}peo[maxn]; 
bool cmp(Peo p1,Peo p2){   
	return p1.arrive<p2.arrive;
}
bool cmp2(Peo p1,Peo p2){ 
	if(p1.sertime==p2.sertime)
		return p1.arrive>p2.arrive;  
	return p1.sertime<p2.sertime;
}
int main(){  
		int n,k,m;   
		scanf("%d",&n);  
		vector<int>vis(n, 0);
		//int* vis = (int*)malloc(sizeof(n));
		//int* vis = new int[n];
		//memset(&vis,0,sizeof(vis)); 
		for(int i=0;i<n;i++){ 
			int h,m,s;   
			scanf("%d:%d:%d %d %d",&h,&m,&s,&peo[i].stay,&peo[i].vip);     
			peo[i].arrive=h*3600+m*60+s;     
			if(peo[i].stay>120)peo[i].stay=120; 
		}    
		scanf("%d %d",&k,&m);  
		fill(tab,tab+k,open);//所有桌子的最早服务时间都设置为早上八点  
		while(m--){      
			int idx;  
			scanf("%d",&idx);
			table[idx-1]=1; 
		} 
		sort(peo,peo+n,cmp); 
		int i=0;  
		while(i<n){ 
			if(vis[i]){  
				i++;       
				continue;  
			}   
			int aimt=tab[0];//有桌子可用的最早时间
			int aimi=0;//目标桌子编号   
			if (peo[i].vip) {
				int j = 0;
				for (; j < k; j++) {
					if (tab[j] <= peo[i].arrive&&table[j]) {
						aimi = j;
						aimt = peo[i].arrive;
						break;
					}
					if (tab[j] < aimt) {//没有空桌时先找结束的最早的一张桌子  
						aimt = tab[j];
						aimi = j;
					}
				}
				if (j == k) {//没有空闲的vip桌,就看普通桌了
					for (j = 0; j < k; j++) {
						if (tab[j] <= peo[i].arrive && !table[j]) {
							aimi = j;
							aimt = peo[i].arrive;
							break;
						}
						if (tab[j] < aimt) {//没有空桌时先找结束的最早的一张桌子  
							aimt = tab[j];
							aimi = j;
						}
					}
				}
			}
			else {//普通用户优先找编号最小的
				for (int j = 0;j < k; j++) {
					if (tab[j] <= peo[i].arrive) {
						aimi = j;
						aimt = peo[i].arrive;
						break;
					}
					if (tab[j] < aimt) {//没有空桌时先找结束的最早的一张桌子  
						aimt = tab[j];
						aimi = j;
					}
				}
			}
			/*
			if(!peo[i].vip&&table[aimi]){//如果被普通用户暂定的这张桌子是vip桌子,就去找有没有vip也在等  
				for(int ii=i+1;ii<n;ii++){    
					if(peo[ii].arrive<=aimt&&peo[ii].vip&&!vis[ii]){//有在等的vip   
						aimp=ii;//vip插队先服务         
						if(peo[ii].arrive>aimt)aimt=peo[ii].arrive;     
						break;     
					}      
				}      
			}   
			*/
			if(aimt<close){   
				serve[aimi]++;
				tab[aimi]=aimt+peo[i].stay*60;  
			}   
			vis[i]=1;   
			peo[i].sertime=aimt;  
			i++;
		}   
		sort(peo,peo+n,cmp2);  
		for(int i=0;i<n;i++){  
			if(peo[i].sertime>=close)continue;  
			printf("%02d:%02d:%02d ",peo[i].arrive/3600,peo[i].arrive%3600/60,peo[i].arrive%60);  
			printf("%02d:%02d:%02d ",peo[i].sertime/3600,peo[i].sertime%3600/60,peo[i].sertime%60);  
			printf("%.0f\n",round((peo[i].sertime-peo[i].arrive)/60.0)); 
		}    
		for(int i=0;i<k;i++){    
			printf("%d",serve[i]);     
			if(i!=k-1)printf(" "); 
		}  
		return 0;
}

编辑于 2020-03-30 11:44:14 回复(0)
(1)求等待时间的时候,pat上面只有大于等于30秒,才向上收,牛客网中的用例不需要
(2)会存在超过两小时的顾客,按照120 min处理
(3)牛客网会存在两个顾客开始服务的时间相同的情况,题目只说了按照开始服务的时间排序,所以最后需要重排一下,时间相同服务时间长的在前面(vip在前面也可以),pat官网上面不需要。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <string>
#include <math.h>
#include <vector>
#include <queue>

using namespace std;
const int maxn = 101;
const int maxp = 10001;
const int INF = 0x3fffffff;
struct Pair {
    int arrive_time;
    int start_service_time;
    int service_time;
    int wait_time;
    int tag;
};
int min_table_num = -1, min_start_time = INF;  /**所有桌子中最早空闲的桌子编号,以及开始空闲的时间*/
int start_time[maxn];  /**每个桌子开始空闲的时间*/
int tables[maxn];  /**每个桌子服务的人数*/
bool isVip[maxn] = {false};  /**当前桌子是不是vip桌子*/
int vip_tables[maxn];   /**存放所有vip桌子编号*/
Pair pairs[maxp];  /**存放所有顾客*/
vector<Pair> result_pairs;
queue<Pair> queue_pairs;  /**存放所有早于min_start_time的非vip顾客*/
queue<Pair> vip_pairs;   /**存放所有早于min_start_time的vip顾客*/

void find_first_service(int table_numbers) {  /**找到所有桌子中最早空闲的桌子*/
    min_table_num = -1, min_start_time = INF;
    for(int j=1; j<=table_numbers; j++) {
        if(start_time[j]<min_start_time) {
            min_start_time = start_time[j];
            min_table_num = j;
        }
    }
}

int findEmptyTable(int isVip, int arriving_time ,int m, int k) {
    int emptyTable = -1;  /**找到当前空闲的桌子*/
    if(isVip == 1) {  /**如果当前用户是vip,就先查找是否有空闲的vip桌子*/
        for(int j=0; j<m; j++) {
            if(start_time[vip_tables[j]]<=arriving_time) {
                emptyTable = vip_tables[j];
                break;
            }
        }
    }
    if(emptyTable == -1) {   /**如果用户不是vip或者没有找到空闲的vip桌子,就选择号码最小的空闲桌子*/
        for(int j=1; j<=k; j++) {
            if(start_time[j]<=arriving_time) {
                emptyTable = j;
                break;
            }
        }
    }
    return emptyTable;
}

int find_EmptyVipTable(int viptable_num, int time) {
    int pos = -1;
    for(int j=0; j<viptable_num; j++) {
        if(start_time[vip_tables[j]]==time) {
            pos = vip_tables[j];
            break;
        }
    }

    return pos;
}

void handle_Pairs(int m,int emptyTable) {
    int vipEmptyPos = find_EmptyVipTable(m, min_start_time);  /**因为存在多个桌子同时最早空闲的情况,需要找到当前是否有vip桌子*/
    Pair temp;
    if(vipEmptyPos == -1 || vip_pairs.empty()) {  //当前空闲的桌子不是vip桌或则当前队列中没有vip,就选择队首
        if(vip_pairs.empty()) {
            temp = queue_pairs.front();
            queue_pairs.pop();
        } else if(queue_pairs.empty()) {
            temp = vip_pairs.front();
            vip_pairs.pop();
        } else {
            Pair p1 = queue_pairs.front();
            Pair p2 = vip_pairs.front();
            if(p1.arrive_time<p2.arrive_time) {
                temp = p1;
                queue_pairs.pop();
            } else {
                temp = p2;
                vip_pairs.pop();
            }
        }
    } else {   /**当前最早空闲的桌子是vip桌子且队列中有vip用户*/
        temp = vip_pairs.front();
        vip_pairs.pop();
        emptyTable = vipEmptyPos;
    }

    temp.wait_time = start_time[emptyTable] - temp.arrive_time;
    temp.start_service_time = temp.wait_time+temp.arrive_time;
    result_pairs.push_back(temp);

    start_time[emptyTable] += temp.service_time*60;
    tables[emptyTable]++;
}

bool cmp(Pair a, Pair b) {
    return a.arrive_time<b.arrive_time;
}
bool cmp2(Pair a, Pair b) {
    if(a.start_service_time != b.start_service_time)
        return a.start_service_time<b.start_service_time;
    else
        return a.tag>b.tag;
}
bool cmp3(int a, int b) {
    return a<b;
}

int main() {
    int n;
    int open_time = 8*3600, close_time = 21*3600;

    scanf("%d", &n);
    for(int i=0; i<n; i++) {
        int h,m,s;
        scanf("%d:%d:%d %d %d",&h,&m,&s,&pairs[i].service_time,&pairs[i].tag);
        if(pairs[i].service_time > 120)
            pairs[i].service_time = 120;
        pairs[i].arrive_time = h*3600+m*60+s;
    }
    int k,m;
    scanf("%d %d", &k, &m);
    for(int i=0; i<m; i++) {
        int vip_num;
        scanf("%d",&vip_num);
        vip_tables[i] = vip_num;
        isVip[vip_num] = true;
    }

    sort(pairs, pairs+n, cmp);  /**所有顾客按照到达先后时间排序*/
    sort(vip_tables, vip_tables+m, cmp3);
    fill(start_time+1,start_time+k+1, open_time);
    fill(tables+1, tables+k+1, 0);

    int len = min(k,n);
    int start_index = 0;

    for(int i=0; i<len; i++,start_index++) { /**将前k对顾客直接进行服务(打乒乓球)*/
        int arrive = pairs[i].arrive_time;
        if(arrive >= close_time) {
            start_index = max(k,n);
            break;
        }
        int emptyTable = findEmptyTable(pairs[i].tag, arrive, m, k);

        start_time[emptyTable] = pairs[i].service_time*60 + arrive;
        pairs[i].wait_time = 0;
        pairs[i].start_service_time = pairs[i].arrive_time;
        result_pairs.push_back(pairs[i]);
        tables[emptyTable]++;
    }

    bool isNeedRefresh = true;
    for(int i=start_index; i<n;) {
        int arriving_time = pairs[i].arrive_time;
        if(isNeedRefresh) {
            find_first_service(k);   /**找到当前最早空闲的桌子*/
        }
        if(min_start_time >= close_time || arriving_time>=close_time) /**如果最早空闲的时间或则当前用户的到达时间达到关门时间,终止循环*/
            break;

        if( arriving_time <= min_start_time) {  /**如果当前顾客到达时间早于最早空闲时间,则入队等待*/
            if(pairs[i].tag == 1) {
                vip_pairs.push(pairs[i]);
            } else {
                queue_pairs.push(pairs[i]);
            }
            isNeedRefresh = false;
            i++;
        } else {   /**否则,需要处理当前排队中的客户*/
            if(!queue_pairs.empty() || !vip_pairs.empty()) {  /**如果当前队列不为空*/
                handle_Pairs(m, min_table_num);
                isNeedRefresh = true;
            } else {     /**如果当前队列为空,则当前用户根据身份(是否是vip)直接选择空闲桌子进行*/
                int emptyTable = findEmptyTable(pairs[i].tag, arriving_time, m, k);

                start_time[emptyTable] = pairs[i].service_time*60 + arriving_time;
                tables[emptyTable]++;
                pairs[i].wait_time = 0;
                pairs[i].start_service_time = pairs[i].arrive_time;
                result_pairs.push_back(pairs[i]);
                i++;
                isNeedRefresh = true;
            }
        }
    }

    while(!queue_pairs.empty() || !vip_pairs.empty()) { /***/
        find_first_service(k);

        if(min_start_time >= close_time)
            break;
        handle_Pairs(m, min_table_num);
    }

    sort(result_pairs.begin(), result_pairs.end(), cmp2);
    for(int i=0; i<result_pairs.size(); i++) {
        int wait_minutes = result_pairs[i].wait_time/60;
        if(result_pairs[i].wait_time%60 >=30)
            wait_minutes++;
        int arrive = result_pairs[i].arrive_time;
        int start_service = result_pairs[i].start_service_time;
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",arrive/3600,(arrive%3600)/60, arrive%60,start_service/3600,(start_service%3600)/60, start_service%60,wait_minutes);
    }

    for(int i=1; i<k; i++) {
        printf("%d ",tables[i]);
    }
    printf("%d",tables[k]);
}



发表于 2019-08-29 14:17:20 回复(0)
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

const int N = 10000 + 10, K = 100 + 10;
const int START = 28800, END = 75600;
struct Tables {
    int k;
    int tags[K], stat[K], cnt[K];
    Tables()
    {
        memset(stat, 0, sizeof(stat));
        memset(cnt, 0, sizeof(cnt));
    }
    void init(int kk)
    {
        k = kk;
        for(int i = 0; i < K; i++) {
            tags[i] = 0b01;
        }
    }
    void tagj(int j)
    {
        tags[j] = 0b10;
    }
    int isfree(int t, int tagm)
    {
        for(int i = 0; i < k; i++) {
            if((tags[i] & tagm) && stat[i] <= t) {
                return i;
            }
        }
        return -1;
    }
    void take(int id, int et)
    {
        stat[id] = et;
        cnt[id]++;
    }
};
struct Players {
    static const int maxN = END + 10;
    int pt[maxN], tags[maxN]; //use arriving time as index
    Players()
    {
        memset(pt, 0, sizeof(pt));
        memset(tags, -1, sizeof(tags));
    }
    int arrived(int t, int *tag)
    {
        if(tags[t] != -1) {
            *tag = tags[t];
            return 1;
        } else {
            return 0;
        }
    }
};
int n, k, m;
Tables tables;
Players players;
queue<int> p[2];
void PrintT(int a, const char *s)
{
    int hh, mm, ss;
    hh = a / 3600; a %= 3600;
    mm = a / 60; a %= 60;
    ss = a;
    printf(s, hh, mm, ss);
}
void servplayer(int table, int t, int tag)
{
    int at = p[tag].front(); p[tag].pop();

    PrintT(at, "%02d:%02d:%02d ");
    PrintT(t, "%02d:%02d:%02d ");
    int delta = (t - at + 30) / 60;
    printf("%d\n", delta);

    int pt = players.pt[at];
    tables.take(table, t + pt);
}
int main()
{
    scanf("%d", &n);
    for(int i = 0; i < n; i++) {
        int hh, mm, ss, playt, tag;
        scanf("%d:%d:%d%d%d", &hh, &mm, &ss, &playt, &tag);
        int t = hh * 3600 + mm * 60 + ss;
        if(t < END && t >= START) {
            players.pt[t] = (playt >= 2 * 60) ? 2 * 3600 : playt * 60;
            players.tags[t] = tag;
        }
    }
    scanf("%d%d", &k, &m);
    tables.init(k);
    for(int i = 0; i < m; i++) {
        int j;
        scanf("%d", &j);
        tables.tagj(j - 1);
    }
    for(int t = START; t < END; t++) {
        int tag;
        if(players.arrived(t, &tag)) {
            p[tag].push(t);
        }
        int table = -1;
        while(!p[1].empty() &&\
        (table = tables.isfree(t, 0b10)) != -1) { //preemption
            servplayer(table, t, 1);
        }
        while((table = tables.isfree(t, 0b11)) != -1) {
            if(!p[1].empty() && (p[0].empty() || p[1].front() <= p[0].front())) {
                servplayer(table, t, 1);
            } else if(!p[0].empty()) {
                servplayer(table, t, 0);
            } else {
                break;
            }
        }
    }
    for(int i = 0; i < k; i++) {
        if(i) {
            printf(" ");
        }
        printf("%d", tables.cnt[i]);
    }
    printf("\n");
    return 0;
}

PAT数据坑在于rounded up to是按照大于等于30秒,进一分钟,小于30秒则舍去的原则
编辑于 2017-08-21 18:26:01 回复(0)
啥头像
要注意的事项:
        1. “每个人玩的时间不要超过两个小时 ”这个限制要用上,有测试用例有这个。超过两小时时算两小时。

主要思路:
        1.首先设置Player类和Table类记录运动员和桌子的一些情况;
        2.有两个时间会触动处理程序,第一种运动员到达,第二种是有空闲桌子了。这两个时间可以用一个时间戳TimeStamp类来记录处理。  用set来自动排序
        3.vip问题,只有当队列中vip运动员,且此时刚好有vip的桌子时,优先考虑把vip运动员分配到vip桌子上去。
        4.然后就是选哪个桌子,选哪个运动员的问题了

代码如下:
#include <iostream>
#include <queue>
#include <vector>
#include <set>
#include <stdio.h>
#include <algorithm>

using namespace std;

struct Player
{
    int arrivingTime, servingTime, playingTime;
    int isVip;
    bool operator<(const Player& that) const {
        return (arrivingTime < that.arrivingTime);
    }
};

struct Table
{
    int id, time, servedPlayers;
    int isVip;
    Table() {
        isVip = false; servedPlayers = 0;
        time = 0;
    }
};

struct TimeStamp
{
    int time; bool isPlayer;
    TimeStamp(){}
    TimeStamp(int _time, bool _isPlayer) {
        time = _time; isPlayer = _isPlayer;
    }
    bool operator<(const TimeStamp& that) const {
        return (time<that.time);
    }
};

int main()
{
    // 读入数据
    int N, K, M; scanf("%d", &N);
    Player players[N]; multiset<TimeStamp> ts;
    int hour, minu, sec, time;
    for(int i=0; i<N; i++) {
        scanf("%d:%d:%d", &hour, &minu, &sec);
        time = 3600*hour + 60*minu + sec;
        players[i].arrivingTime = time;
        ts.insert(TimeStamp(time, true));
        scanf("%d", &time); time *= 60;
        time = min(time, 7200);
        players[i].playingTime = time;
        scanf("%d", &players[i].isVip);
    }
    scanf("%d %d", &K, &M); int vip;
    vector<Table> tables(K);
    //Table tables[K];
    for(int i=0; i<K; i++) {
        tables[i].id = i+1;
    }
    for(int i=0; i<M; i++) {
        scanf("%d", &vip);
        tables[vip-1].isVip = true;
    }

    // 处理数据
    sort(players, players+N); int idx = 0;
    vector<int> servedPlayerIdx; TimeStamp timeStamp;
    int id; bool hasTable; Table tempTable;
    queue<int> que; queue<int> vipQue;
    while(!ts.empty()) {
        timeStamp = *ts.begin(); ts.erase(ts.begin());
        if(timeStamp.isPlayer) {
            if(players[idx].isVip) {
                vipQue.push(idx);
            } else {
                que.push(idx);
            }
            idx++;
        }
        hasTable = false;
        // 选空闲桌子
        // 处理vip的特殊情况
        if(!vipQue.empty()) {
            for(int j=0; j<K; j++) {
                if(tables[j].time <= timeStamp.time && tables[j].isVip) {
                    tempTable = tables[j];
                    hasTable = true; break;
                }
            }
        }
        // 若没有,按普通情况处理
        if(!hasTable) {
            for(int j=0; j<K; j++) {
                if(tables[j].time <= timeStamp.time) {
                    tempTable = tables[j];
                    hasTable = true; break;
                }
            }
        }
        if(hasTable && (!vipQue.empty()||!que.empty())) {
            // 选符合条件的运动员
            if(tempTable.isVip) {
                if(!vipQue.empty()) {
                    id = vipQue.front(); vipQue.pop();
                } else {
                    id = que.front(); que.pop();
                }
            } else {
                if(!vipQue.empty()) {
                    if(!que.empty() && (que.front() < vipQue.front())) {
                        id = que.front(); que.pop();
                    } else {
                        id = vipQue.front(); vipQue.pop();
                    }
                } else {
                    id = que.front(); que.pop();
                }
            }
            // 时间等数据处理
            tempTable.time = max(tempTable.time, players[id].arrivingTime);
            if(tempTable.time < 75600) {
                servedPlayerIdx.push_back(id);
                tables[tempTable.id-1].servedPlayers++;
            }
            players[id].servingTime = tempTable.time;
            tempTable.time += players[id].playingTime;
            tables[tempTable.id-1].time = tempTable.time;
            ts.insert(TimeStamp(tempTable.time, false));
        }
    }

    // 输出结果
    int arrivingTime, servingTime, waitingTime;
    for(int i=0; i<servedPlayerIdx.size(); i++) {
        id = servedPlayerIdx[i];
        arrivingTime = players[id].arrivingTime;
        servingTime = players[id].servingTime;
        waitingTime = servingTime - arrivingTime;
        printf("%02d:%02d:%02d ", arrivingTime/3600,\
                (arrivingTime%3600)/60, arrivingTime%60);
        printf("%02d:%02d:%02d ", servingTime/3600,\
                (servingTime%3600)/60, servingTime%60);
        printf("%d\n", (waitingTime+59)/60);
    }
    for(int i=0; i<K; i++) {
        if(i) {
            printf(" ");
        }
        printf("%d", tables[i].servedPlayers);
    }

    return 0;
} 


编辑于 2015-12-18 20:23:54 回复(7)
思路:VIP在有空余的VIP桌时是爸爸。
第一次一遍做对PAT的模拟题~开心~
牛客网有一个样例俩开始服务时间是相同的,用`sort`函数排序时候要在`cmp`里面用小于等于!PAT都不卡这个数据,牛客网你够了!
#include<iostream>
#include<map>
#include<vector>
#include<queue>
#include<algorithm>

using namespace std;

struct cus {
    int timestamp;
    int starttime = -1;
    int durinsec;
    bool isvip;
};

bool cmp(cus c1, cus c2) {
    // It is guaranteed that the arriving time is between 08:00:00 and 21:00:00 while the club is open.
    // It is assumed that no two customers arrives at the same time.
    return c1.timestamp < c2.timestamp;
}

bool cmp2(cus c1, cus c2) {
    // 如果这里不加等号牛客网的样例过不去
    return c1.starttime <= c2.starttime;
}

int main() {
    // std::ios::sync_with_stdio(false);
    // std::cin.tie(0);

    int N;
    cin >> N;
    vector<cus> v;
    v.resize(N);
    for(int i = 0; i < N; i++) {
        int h, m, s, durinmin;
        char c;
        cin >> h >> c >> m >> c >> s >> durinmin >> v[i].isvip;
        v[i].timestamp = h*3600 + m*60 + s;
        if(durinmin > 120)
            durinmin = 120;
        v[i].durinsec = durinmin * 60;
    }

    int table_num, vip_table_num;
    cin >> table_num >> vip_table_num;
    vector<int> table_is_vip, table_occupied, table_serve_num;
    table_is_vip.resize(table_num, 0);
    table_occupied.resize(table_num, -1);
    table_serve_num.resize(table_num, 0);
    for (int j = 0; j < vip_table_num; ++j) {
        int a;
        cin >> a;
        table_is_vip[a-1] = 1;
    }

    sort(v.begin(), v.end(), cmp);
    queue<int> oq, vq;
    for (int k = 0; k < v.size(); ++k)
        v[k].isvip ? vq.push(k) : oq.push(k);

    for(int now = 8*3600; now < 21*3600; now++) {
        // 送客
        for (int j = 0; j < table_num; ++j) {
            if(table_occupied[j] != -1) {
                int who_is_here = table_occupied[j];
                if(v[who_is_here].starttime + v[who_is_here].durinsec == now) {
                    table_occupied[j] = -1;
                }
            }
        }

        // 迎客
        // 看vip是否和vip桌同时出现
        bool vip_and_vip_table = false;
        if (!vq.empty() && v[vq.front()].timestamp <= now) {
            for (int j = 0; j < table_num; ++j) {
                if (table_occupied[j] == -1 && table_is_vip[j]) {   // vip见到了vip桌 最优先事项 直接分配
                    int who = vq.front();
                    table_occupied[j] = who;
                    vq.pop();
                    v[who].starttime = now;
                    table_serve_num[j]++;

                    vip_and_vip_table = true;
                    break;
                }
            }
        }
        if(vip_and_vip_table) {
            // 可能会有多个客人同时进场 此时需要再次循环至此 无需在一次循环后加时间
            now--;
            continue;
        }

        // 是不是vip都来排普通队
        // 看看两个队列 不会同时到 但是会阻塞
        // 先普通队
        int who_is_coming_o = -1;
        int which_table_it_want_o = -1;
        int come_time_o = -1;
        if (!oq.empty() && v[oq.front()].timestamp <= now) {
            for (int j = 0; j < table_num; ++j) {
                // 因为没有vip桌或者没有vip了 直接看所有的就好
                if (table_occupied[j] == -1) {
                    which_table_it_want_o = j;
                    who_is_coming_o = oq.front();
                    come_time_o = v[who_is_coming_o].timestamp;
                    break;
                }
            }
        }
        // 再vip队
        int who_is_coming_v = -1;
        int which_table_it_want_v = -1;
        int come_time_v = -1;
        if (!vq.empty() && v[vq.front()].timestamp <= now) {
            for (int j = 0; j < table_num; ++j) {
                // 因为没有vip桌或者没有vip了 直接看所有的就好
                if (table_occupied[j] == -1) {
                    which_table_it_want_v = j;
                    who_is_coming_v = vq.front();
                    come_time_v = v[who_is_coming_v].timestamp;
                    break;
                }
            }
        }
        // 判断一下谁来的早
        if(who_is_coming_o != -1 && who_is_coming_v != -1) {
            if (come_time_o < come_time_v) {
                oq.pop();
                table_occupied[which_table_it_want_o] = who_is_coming_o;
                v[who_is_coming_o].starttime = now;
                table_serve_num[which_table_it_want_o]++;

                // 可能会有多个客人同时进场 此时需要再次循环至此 无需在一次循环后加时间
                now--;
                continue;
            } else {
                vq.pop();
                table_occupied[which_table_it_want_v] = who_is_coming_v;
                v[who_is_coming_v].starttime = now;
                table_serve_num[which_table_it_want_v]++;

                // 可能会有多个客人同时进场 此时需要再次循环至此 无需在一次循环后加时间
                now--;
                continue;
            }
        } else if (who_is_coming_o != -1) {
            oq.pop();
            table_occupied[which_table_it_want_o] = who_is_coming_o;
            v[who_is_coming_o].starttime = now;
            table_serve_num[which_table_it_want_o]++;

            // 可能会有多个客人同时进场 此时需要再次循环至此 无需在一次循环后加时间
            now--;
            continue;
        } else if (who_is_coming_v != -1) {
            vq.pop();
            table_occupied[which_table_it_want_v] = who_is_coming_v;
            v[who_is_coming_v].starttime = now;
            table_serve_num[which_table_it_want_v]++;

            // 可能会有多个客人同时进场 此时需要再次循环至此 无需在一次循环后加时间
            now--;
            continue;
        }
    }

    // Notice that the output must be listed in chronological order of the serving time.
    sort(v.begin(), v.end(), cmp2);
    for(int i = 0; i < N; i++) {
        if(v[i].starttime == -1)
            continue;
        printf("%02d:%02d:%02d ", v[i].timestamp/3600, (v[i].timestamp/60) % 60, v[i].timestamp % 60);
        printf("%02d:%02d:%02d ", v[i].starttime/3600, (v[i].starttime/60) % 60, v[i].starttime % 60);
        printf("%.0f\n", (v[i].starttime - v[i].timestamp) / 60.0 + 0.000001) ;
    }
    cout << table_serve_num[0];
    for(int i = 1; i < table_num; i++)
        cout << ' ' << table_serve_num[i];
    cout << endl;

    return 0;
}


发表于 2020-09-19 14:57:23 回复(0)
求大神解答。。牛客过了 pat上最后一个测试点不对
//Table Tennis (30分)
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;
const int INF = 0x3f3f3f3f;
int n, k, m;
int vip[1024], use[1024], tables[1024];//桌子vip状态(是否是vip桌子),每个桌子使用次数,每个桌子用完的时间
struct table {
    int arrive, paly, con, wait;
    int h, m, s;
    int ok;
};
vector<struct table> array;

bool comp(struct table &a, struct table &b) {
    if(a.arrive==b.arrive) return a.wait<b.wait;
    else return a.arrive < b.arrive;
}

int v_(int i) {//判断是否还有更小的vip桌子
    int j;
    for (j = 1; j <= k; j++) {
        if (vip[j] == 1 && array[i].arrive >= tables[j]) {
            array[i].ok = 1;
            array[i].wait += 0;
            tables[j] = array[i].arrive + array[i].paly * 60;
            use[j]++;
            break;
        }
    }
    return j;
}

int nv_(int i) {//判断是否还有更小的非vip桌子
    int j;
    for (j = 1; j <= k; j++) {
        if (vip[j] == 0 && array[i].arrive >= tables[j]) {
            array[i].ok = 1;
            array[i].wait += 0;
            tables[j] = array[i].arrive + array[i].paly * 60;
            use[j]++;
            break;
        }
    }
    return j;
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        struct table node;
        scanf("%d:%d:%d %d %d", &node.h, &node.m, &node.s, &node.paly, &node.con);
        node.arrive = node.h * 3600 + node.m * 60 + node.s;
        if (node.paly > 120) node.paly = 120;//超过两小时按两小时算
        node.wait = 0;
        node.ok = 0;//是否被遍历过
        if (node.arrive < 21 * 3600) array.push_back(node);
    }
    cin >> k >> m;
    memset(vip, 0, sizeof(vip));
    memset(use, 0, sizeof(use));
    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        vip[x] = 1;
    }
    memset(tables, 8 * 3600, sizeof(tables));
    sort(array.begin(), array.end(), comp);
    int number = array.size();
    for (int i = 0; i < number; i++) {//在8点之前到的
        if (array[i].h < 8) {
            array[i].wait += (8 * 3600) - array[i].arrive;
            array[i].arrive = 8 * 3600;
        }
    }
    for (int i = 0; i < number; i++) {
        if (array[i].ok == 1) continue;
        int min = INF, index = 0;
        for (int j = 1; j <= k; j++) {//找到最早完成服务的桌子
            if (tables[j] < min) {
                min = tables[j];
                index = j;
            }
        }
        if (min >= 21 * 3600) break;
        if (array[i].arrive < min) {//顾客在最早服务完之前已经到了
            int tt = 0;
            if (array[i].con == 0 && vip[index] == 1) {//如果最早服务完的是vip桌子并且队列的第一个是非vip用户
                for (int j = i + 1; j < number; j++) {//遍历排在他后边的顾客是不是有vip用户并且已经到了的
                    if (array[j].arrive <= min && array[j].con == 1) {
                        array[j].ok = 1;
                        array[j].wait = tables[index] - array[j].arrive;
                        tables[index] += array[j].paly * 60;
                        array[j].arrive += array[j].wait;
                        use[index]++;
                        i = i - 1;
                        tt = 1;
                        break;
                    }
                }
            }
            if (tt == 0) {//如果后边没有人排队
                array[i].ok = 1;
                array[i].wait = tables[index] - array[i].arrive;
                tables[index] += array[i].paly * 60;
                array[i].arrive += array[i].wait;
                use[index]++;
            }
        } else {//如果顾客比最早服务完的桌子来得晚
            if (array[i].con == 1) {//vip用户
                if (vip[index] == 1) {//vip桌子
                    v_(i);//判断是否有号子更小的vip桌子
                } else {//非vip桌子
                    int j = v_(i);//先判断有没有空的vip桌子(因为不知道有没有空的VIP桌子)
                    if (j == k + 1) {//没有空着的vip的桌子
                        nv_(i);//判断是否有号子更小的非vip桌子
                    }
                }
            } else {//非vip用户
                for(int j=1;j<=k;j++){
                    if(array[i].arrive>tables[j]){
                        array[i].ok = 1;
                        array[i].wait += 0;
                        tables[j] = array[i].arrive + array[i].paly * 60;
                        use[j]++;
                        break;
                    }
                }
            }
        }
    }
    sort(array.begin(), array.end(), comp);
    for (int i = 0; i < number; i++) {
        if (array[i].ok != 1) continue;
        int time = array[i].wait, H = 0, M = 0, t = 0;
        while (time >= 60) {
            time -= 60;
            t++;
        }
        if (time >= 30) t++;
        while (array[i].arrive >= 3600) {
            array[i].arrive -= 3600;
            H++;
        }
        while (array[i].arrive >= 60) {
            array[i].arrive -= 60;
            M++;
        }
        printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", array[i].h, array[i].m, array[i].s, H, M, array[i].arrive, t);
    }
    for (int i = 1; i <= k; i++) {
        if (i == 1) cout << use[i];
        else cout << " " << use[i];
    }
}


发表于 2020-02-19 09:48:15 回复(0)
这个题对于我最大的一个坑是:vip用户需要先到vip桌子中去找,如果找不到再到普通桌子中去找;而普通用户只需要按照序号从小到大找就行了,唯一的限制就是如果找到的桌子是vip桌子,需要考虑是否有vip用户在等这张桌子。以下是我解这道题的大致思路:
首先将用户按照到来的时间先后顺序排序(到达时间在关门时间或之后的用户在输入时已经被过滤掉),做好这个之后,就开始一个用户接一个用户的处理了。
判断用户类型,
如果是vip, 先找结束时间在其到达或之前的桌子(先到vip桌子中找,再到普通桌子中找,桌子序号分别从小到大),找到就退出,如果没有找到,说明所有桌子都被占,需要排队,则查找结束时间最早的桌子,因为必定在这张桌子上排队;
如果是普通用户,处理过程类似,不过查找是按桌子序号从小到大找,不区分vip桌子和普通桌子。不过若普通用户找到的结束时间最早的桌子是vip桌子,则需要让后面等待这张桌子的vip用户先用(如果有的话)。这里判断是否处于同一张桌子的队列中是通过比较用户的到达时间和桌子的结束时间,如果到达时间小于桌子的结束时间,则一定处于等待该桌子的队列中,基于这个规则查找后续的vip用户,如果找到,则处理该vip用户,为了避免重复访问,设置标记,当前普通用户则等到下一轮再进行处理。
附上代码:
#include <cstdio>
#include <algorithm>

#define T 75600
#define ST 28800

struct Table{
	int endt; //结束时间
	int count; //服务计数
};

struct PP{
	int arrvt;
	int servt;
	int playt;
	int tag;
	int id;
};

Table tables[102]; //桌子
PP pps[10002]; //用户
int ppsv[10002]; //访问标记
int vots[102]; //vip桌子和普通桌子序列
int vois[102]; //桌子类型标记,1为vip桌子,0为普通桌子

bool cmp(PP &a, PP &b){
	return a.arrvt<b.arrvt;
}

bool cmp2(PP &a, PP &b){
	if(a.servt!=b.servt) 
		return a.servt<b.servt;
	else
		return a.arrvt>b.arrvt;
}

//判断普通用户 i 后是否有vip用户在等待同张桌子,若有,则返回vip用户序号,否则返回0
int anyvip(int t,int i){
	int z=0;
	for(int j=i+1;pps[j].arrvt<t;j++){
		if(!ppsv[j]&&pps[j].tag==1){
			z=j;
			break;
		}
	}
	return z;
}

//更新用户和桌子记录
void upd(int i,int j,int t){
	pps[i].servt = t;
	tables[j].endt = t+pps[i].playt;
	tables[j].count += 1;
}

int main(){
	int n,m,K,i;
	scanf("%d",&n);
	i=0;
	for(int j=0;j<n;++j){
		int h,m,s,p,t,ts;
		scanf("%d:%d:%d%d%d",&h,&m,&s,&p,&t);
		ts=h*3600+m*60+s;
		if(ts<T){
			pps[i].arrvt = ts;
			pps[i].playt = p>120?7200:p*60;
			pps[i].tag = t;
			i++;
		}
	}
	n=i;
	scanf("%d%d",&K,&m);
	i=0;
	for(int j=0;j<m;++j){
		int b;
		scanf("%d",&b);
		if(!vois[b]){
			vots[i++]=b;
			vois[b] = 1;
		}
	}
	m=i;
	for(int j=1;j<=K;++j)
		if(vois[j]==0)
			vots[i++] = j;
	std::sort(vots,vots+m);
	std::sort(vots+m,vots+K);
	std::sort(pps,pps+n,cmp);
	for(i=1;i<=K;++i)
		tables[i].endt = ST;
	for(i=0;i<n;++i){
		int t;
		if(ppsv[i])
			continue;
		if(pps[i].tag==1){
			int t1=0;
			for(int k=0;k<K;++k){
				t=vots[k];
				if(pps[i].arrvt>=tables[t].endt){
					t1=t;
					break;
				}
			}
			if(t1){
				upd(i,t1,pps[i].arrvt);
				ppsv[i] = 1;
			}
			else{
				int mm;
				t1=0;
				mm=T;
				for(int k=0;k<K;++k){
					t=vots[k];
					if(tables[t].endt<mm){
						mm = tables[t].endt;
						t1=t;
					}
				}
				if(t1!=0){
					upd(i,t1,tables[t1].endt);
					ppsv[i] = 1;
				}
			}
		}else{
			int t2=0;
			for(int k=0;k<K;++k){
				t=k+1;
				if(pps[i].arrvt>=tables[t].endt){
					t2=t;
					break;
				}
			}
			if(t2){
				upd(i,t2,pps[i].arrvt);
				ppsv[i] = 1;
			}else{
				int mm;
				t2=0;
				mm=T;
				for(int k=0;k<K;++k){
					t=k+1;
					if(tables[t].endt<mm){
						mm = tables[t].endt;
						t2=t;
					}
				}
				if(t2!=0){
					int j=i;
					if(vois[t2]==1){
						j=anyvip(tables[t2].endt,i);
						if(j==0)
							j=i;
					}
					upd(j,t2,tables[t2].endt);
					ppsv[j] = 1;
					if(j!=i)
						i--;
				}	
			}
		}
	}
	for(int i=0;i<n;++i)
		pps[i].id = i;
	std::sort(pps,pps+n,cmp2);
	for(int j=0;j<n;++j){
		i=j;
		if(ppsv[pps[i].id])
			printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",
				pps[i].arrvt/3600,pps[i].arrvt%3600/60,pps[i].arrvt%60,
				pps[i].servt/3600,pps[i].servt%3600/60,pps[i].servt%60,
				(int)((pps[i].servt-pps[i].arrvt)/(float)60+0.5));
	}
	printf("%d",tables[1].count);
	for(i=2;i<=K;++i)
		printf(" %d",tables[i].count);
	return 0;
}

编辑于 2019-09-04 22:14:22 回复(0)
感觉pat官网加强了数据,
不晓得为啥,好多题牛客可以过,但是pat就是有几组过不了



#include<bits/stdc++.h>
#define _start 28800
#define _end 75600
#define inf 0x3f3f3f3f
using namespace std;
struct Node{         int total, need;     friend bool operator < (const Node &a, const Node &b){         return a.total > b.total;     }
}node;
struct Edge{     int endtime;     int id;     friend bool operator < (const Edge &a, const Edge &b){         return a.endtime > b.endtime;//从小到大排序     }
}edge;
priority_queue<Node> q1,q0;
priority_queue<Edge> e0;
priority_queue<int, vector<int>, greater<int> > free_r,vip_r;
int n,x,y;
int an[105];
int vis[105];
int main(){     scanf("%d", &n);     int h,f,m,val,k;     for(int i = 0; i < n; i++){         scanf("%d:%d:%d",&h,&f,&m);         scanf("%d %d",&val, &k);         node.total = h*60*60+f*60+m;         if(val <= 120)             node.need = val*60;         else             node.need = 120*60;         if(k){             q1.push(node);         }else             q0.push(node);     }     scanf("%d%d",&x,&y);     int p;     for(int i = 0; i < y; i++){         scanf("%d", &p);         an[p] = 1;     }     for(int i = 1; i <= x; i++){         if(an[i])             vip_r.push(i);         else             free_r.push(i);     }     for(int time = _start; time < _end; time++){         while(!e0.empty()&&e0.top().endtime <= time){             if(an[e0.top().id]){                 vip_r.push(e0.top().id);             }else{                 free_r.push(e0.top().id);             }             e0.pop();         }         while((!q1.empty()&&q1.top().total <= time) || (!q0.empty()&&q0.top().total <= time)){             int a = inf,b = inf;             if((!q1.empty()&&q1.top().total <= time)){                 a = q1.top().total;             }             if((!q0.empty()&&q0.top().total <= time)){                 b = q0.top().total;             }             if(a != inf){ //a 为VIP                 int id = 0;                 if(!vip_r.empty()){                     id = vip_r.top();                     vip_r.pop();                 }else if(!free_r.empty()){                     id = free_r.top();                     free_r.pop();                 }                 if(id){                     int ans = time + q1.top().need;                     vis[id] ++;                     int miniute = (time - a)/60 + ((time - a)%60 >= 30?1:0);                     printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", a/3600, (a%3600)/60, a%60, time/3600, (time%3600)/60, time%60, miniute);                     e0.push({ans, id});                     q1.pop();                 }else{                     break;                 }                              }else{    //b为非VIP                 int id = 0;                 if(!free_r.empty() || !vip_r.empty()){                     int a1 = inf, a2 = inf;                     if(!free_r.empty())                         a1 = free_r.top();                     if(!vip_r.empty())                         a2 = vip_r.top();                     if(a1 < a2){                         id = a1;                         free_r.pop();                     }else{                         id = a2;                         vip_r.pop();                     }                 }                 if(id){                     int ans = time + q0.top().need;                     vis[id] ++;                     int miniute = (time - b)/60 + ((time - b)%60 >= 30?1:0);                     printf("%02d:%02d:%02d %02d:%02d:%02d %d\n", b/3600, (b%3600)/60, b%60, time/3600, (time%3600)/60, time%60, miniute);                     e0.push({ans, id});                     q0.pop();                 }else{                     break;                 }             }         }     }     for(int i = 1; i <= x; i++)         printf("%d%c", vis[i], i==x?'\n':' ');     return 0;
}

发表于 2019-06-23 14:06:51 回复(0)
求解答:pat第三和最后两个点过不了,牛客AC了
大致思路就是取一个玩家放进等待队列,然后检查是否有空桌,如果没有进去下一步,取下个玩家
进入的时间,在当前玩家的时间和下个玩家之间,是否有空桌,按照最早结束的时间来分配
这些桌子,所有的分配顺序都是先检查是否有vip桌,有vip桌然后检查是否有vip玩家,没有
vip桌,检查是否有vip玩家。



#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
typedef struct person {
    int start, arrive, end;
    int time;
    bool vip;
    int id;
}person;
typedef struct table {
    int num;
    int end;
    bool vip;
    bool isbusy;
}table;
vector<person> persons;
vector<table> tables;
vector<person> waitlist;
int n;//人
int k;//桌子数

bool cmp(person a, person b)
{
    return (a.arrive < b.arrive);
}

bool cmp2(person p1, person p2)
{
    return (p1.end - p1.time < p2.end - p2.time);
}

int findvperson()
{
    int i;
    for (i = 0; i < waitlist.size(); i++)
    {
        if (waitlist[i].vip == true)
            return i;
    }
    return -1;
}
int main()
{
    int i, j;
    cin >> n;
    for (i = 0; i < n; i++)
    {
        person tmp;
        int hh, mm, ss; //时间
        int t, vip;  //time vip
        scanf_s("%d:%d:%d %d %d", &hh, &mm, &ss, &t, &vip);
        tmp.arrive = 3600 * hh + 60 * mm + ss;
        tmp.time = t * 60;
        if (tmp.arrive > 21 * 60 * 60)
            continue;
        if (tmp.time > 120 * 60)
            tmp.time = 7200;
        tmp.vip = (vip == 1 ? true : false);
        persons.push_back(tmp);
    }
    int m;
    cin >> k >> m;
    tables.resize(k);
    for (i = 0; i < k; i++)
    {
        tables[i].num = 0;
        tables[i].end = 8 * 3600;
        tables[i].vip = false;
        tables[i].isbusy = false;

    }
    for (i = 0; i < m; i++)
    {
        int vipnum;
        cin >> vipnum;
        tables[vipnum - 1].vip = true;
    }
    sort(persons.begin(), persons.end(), cmp);
    for (i = 0; i < n; i++)
        persons[i].id = i;

    int cnt = 0;
    while (cnt < n)
    {
        int atime = persons[cnt].arrive;
        int index = -1, vindex = -1;
        while (atime == persons[cnt].arrive)
        {
            waitlist.push_back(persons[cnt]);
            cnt++;
            if (cnt == n)
                break;
        }    
        for (i = 0; i < k; i++)
        {
            if (tables[i].end <= atime)
                tables[i].isbusy = false;
        }
        for (i = 0; i < k; i++)
        {
            if (tables[i].isbusy == false && index == -1)
                index = i;
            if (tables[i].isbusy == false && vindex == -1 && tables[i].vip == true)
                vindex = i;
        }
        if (vindex != -1 &&  findvperson() != -1)
        {
            int p = findvperson();
            int id = waitlist[p].id;
            tables[vindex].isbusy = true;
            tables[vindex].end = persons[id].time + atime;
            persons[id].end = tables[vindex].end;
            persons[id].start = atime;
            waitlist.erase(waitlist.begin() + p);
            if(persons[id].start <21*3600)
                tables[vindex].num++;
        }
        else if ((vindex == -1 || findvperson() == -1) && index != -1)
        {
            tables[index].isbusy = true;
            int p = (findvperson() == -1) ? 0 : findvperson();
            int id = waitlist[p].id;
            tables[index].end = persons[id].time + atime;
            persons[id].end = tables[index].end;
            persons[id].start = atime;
            waitlist.erase(waitlist.begin() + p);
            if(persons[id].start <21*3600)
                tables[index].num++;
        }

        int nextime;
        if (cnt != n)
            nextime = persons[cnt].arrive;
        else
            nextime = 0x3fffffff;
        while (waitlist.size()!=0)
        {
            index = -1; vindex = -1;
            int endtime = nextime;
            for (i = 0; i < k; i++)
            {
                if(endtime > tables[i].end)
                {
                    index = i;
                    endtime = tables[i].end;
                }
            }
            endtime = nextime;
            for (i = 0; i < k; i++)
            {
                if (endtime > tables[i].end && tables[i].vip == true)
                {
                    vindex = i;
                    endtime = tables[i].end;
                }
            }
            if (vindex == -1 && index == -1)
                break;
            if (vindex != -1 && findvperson() != -1)
            {
                int p = findvperson();
                int id = waitlist[p].id;
                persons[id].start = tables[vindex].end;
                tables[vindex].isbusy = true;
                tables[vindex].end = persons[id].time + persons[id].start;
                persons[id].end = tables[vindex].end;
                waitlist.erase(waitlist.begin() + p);
                if(persons[id].start <21*3600)
                    tables[vindex].num++;
            }
            else if ((vindex == -1 || findvperson() == -1) && index != -1)
            {
                tables[index].isbusy = true;
                int p = (findvperson() == -1) ? 0 : findvperson();
                int id = waitlist[p].id;
                persons[id].start = tables[index].end;
                tables[index].end = persons[id].time + tables[index].end;
                persons[id].end = tables[index].end;
                waitlist.erase(waitlist.begin() + p);
                if(persons[id].start <21*3600)
                    tables[index].num++;
            }
        }
    }
    sort(persons.begin(), persons.end(), cmp2);
    for (i = 0; i < n; i++)
    {
        int at = persons[i].arrive;
        int st = persons[i].end - persons[i].time;
        int wait = st - at;
        if (st < 21 * 3600)
            printf("%02d:%02d:%02d %02d:%02d:%02d %.0f\n",
                at / 3600, at % 3600 / 60, at % 60,
                st / 3600, st % 3600 / 60, st % 60, round(wait / 60.0));
    }
    printf("%d", tables[0].num);
    for (i = 1; i < k; i++)
    {
        printf(" %d", tables[i].num);
    }
}




发表于 2019-06-14 09:44:39 回复(3)
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<climits>
using namespace std;
/**
    此题挺复杂,要在短时间内AC更是相当困难(当然是对我这种比较笨的来说),具体思路是根据问题场景模拟出相应的数据结构来处理
    priority_queue:在俱乐部中运动的成员形成优先队列,谁先结束谁弹出,同时结束的vip桌先弹出(从而使排队的vip成员尽快得到服务)
    queue<Member>:分成两部分,vip队列和普通队列,表示满员情况下在队列中等待的成员
    vector<Member>:按到达时间存储所有需要被服务的成员
*/
int getTime(int h, int min, int sec){
    return (h-8)*3600 + min * 60 + sec;
}
void printTimeStr(int totalSecs){
    int h = totalSecs/3600 + 8;
    int min = (totalSecs - (h - 8)*3600)/60;
    int sec = totalSecs - (h-8)*3600 - min * 60;
    printf("%02d:%02d:%02d ",h,min,sec);
}
double getSub(double t1, double t2){
    double res = (t2 - t1)/60;
    return round(res);
}
void printItem(int t1, int t2){
    printTimeStr(t1);printTimeStr(t2);
    printf("%d\n",(int)getSub(t1,t2));
}
class Member{
public:
    int isVip; //是不是vip
    int arvT; //到达时间
    int playT; //运动持续时间
    int endT; //结束时间
    int srvT; //服务时间
    int tableID; //所用的球桌
    int tableRank; //使用的球桌级别(用于endT相同时优先弹出vip桌)
};
bool cmpT(Member &m1, Member &m2){
    return m1.arvT < m2.arvT;
}
struct CMP{
    bool operator()(const Member &m1,const Member &m2){
        if(m1.endT != m2.endT) return m1.endT > m2.endT;
        else if(m1.tableRank != m2.tableRank) return m1.tableRank < m2.tableRank;
        else return m1.arvT > m2.arvT;
    }
};
class Table{
public:
    int rank;
    bool used;
    int served;
    Table():rank(0),used(false),served(0){}
};
//为成员获取球桌的函数(一开始打算用栈模拟两种球桌,但考虑到球桌最多只有100台且小序号优先(用栈有其他预料之外的麻烦,比如释放多个球桌时还需要排序),用遍历获取是较好的选择)
int getTable(Table tbs[],Member &m,int n){
    if(m.isVip){//如果是vip
        for(int i =  1; i <= n ; i++){
            if(tbs[i].rank && !tbs[i].used){
                tbs[i].used = true;
                tbs[i].served ++;
                return i;
            }
        }
    }
    for(int i = 1; i <= n; i++){
        if(!tbs[i].used){
            tbs[i].used = true;
            tbs[i].served ++;
            return i;
        }
    }
    return 0;
}
void printTableServed(Table tbs[],int n){//打印每个球桌的服务次数
    for(int i = 1 ; i <= n; i++){
        if(i == n) printf("%d\n",tbs[i].served);
        else printf("%d ",tbs[i].served);
    }
}
int main(){
    int N,total,vipN;
    scanf("%d",&N);
    vector<Member> members;
    queue<Member> normalQ;
    queue<Member> vipQ;
    priority_queue<Member,vector<Member>,CMP> pq;
    for(int i = 0 ; i < N; i++){
        int h,m,s,playM,vip;
        scanf("%d:%d:%d %d %d",&h,&m,&s,&playM,&vip);
        Member mb;
        mb.arvT = getTime(h,m,s); mb.srvT = mb.arvT;
        mb.isVip = vip; mb.playT = playM; mb.endT = mb.srvT + min(playM * 60,2 * 3600);//这里的srvT和endT还非确切时间
        members.push_back(mb);
    }
    sort(members.begin(),members.end(),cmpT);
    scanf("%d %d",&total,&vipN);
    Table tables[total+1];
    for(int i = 0 ; i < vipN; i++){
        int idx;
        scanf("%d",&idx);
        tables[idx].rank = 1;
    }
    int cur = 0;
    Member out;
    while(cur < members.size() || !(vipQ.empty() && normalQ.empty())){//分成所有参加人员和队列中等待的人员这两部分
      /**1.选人入优先队列*/
      if(vipQ.empty() && normalQ.empty()){//没人排队的情况
          Member mb = members[cur++];
          if(mb.arvT >= 13*3600) break;
          int serveTable = getTable(tables,mb,total);
          mb.tableID = serveTable;
          mb.tableRank = tables[serveTable].rank;
          pq.push(mb);
          printItem(mb.arvT, mb.srvT);
      }else{//有人排队的情况(之前优先队列满员,弹出的out成员有效)
        Member newMb;
        if(tables[out.tableID].rank){//空出vip桌
          if(vipQ.size()){
            newMb = vipQ.front(); vipQ.pop();
          }else{
            newMb = normalQ.front();normalQ.pop();
          }
        }else{//空出的不是vip桌,谁先到谁优先
          if(vipQ.size() && normalQ.size()){
            if(vipQ.front().arvT <= normalQ.front().arvT){
              newMb = vipQ.front();vipQ.pop();
            }else{
              newMb = normalQ.front();normalQ.pop();
            }
          }else if(vipQ.empty()){
            newMb = normalQ.front(); normalQ.pop();
          }else{
            newMb = vipQ.front(); vipQ.pop();
          }
        }
        newMb.srvT = out.endT;
        if(newMb.srvT >= 13*3600) break;
        newMb.endT = newMb.srvT + min(newMb.playT*60,2*3600);
        newMb.tableID = out.tableID;
        newMb.tableRank = tables[out.tableID].rank;
        tables[out.tableID].used = true;
        tables[out.tableID].served ++;
        pq.push(newMb);
        printItem(newMb.arvT,newMb.srvT);
      }
      /**2. 选人出优先队列*/
      //得到下一个的最早到达时间
      if(cur == members.size() && vipQ.empty() && normalQ.empty()) break;
      int latestArv = INT_MAX;
      if(cur < members.size()) latestArv = min(latestArv,members[cur].arvT);
      if(normalQ.size()) latestArv = min(latestArv,normalQ.front().arvT);
      if(vipQ.size()) latestArv = min(latestArv,vipQ.front().arvT);
      while(!pq.empty() && pq.top().endT <= latestArv){
            tables[pq.top().tableID].used = false;
            out = pq.top();pq.pop();
      }//弹出所有已经结束的成员
      //如果此时优先队列还是满的,说明有排队的情况
      if(pq.size() == total){
        while(cur < members.size() && members[cur].arvT <= pq.top().endT){
            if(members[cur].isVip) vipQ.push(members[cur++]);
            else normalQ.push(members[cur++]);
        }
        tables[pq.top().tableID].used = false;
        out = pq.top(); pq.pop();
      }
    }
    printTableServed(tables,total);
    return 0;
}

发表于 2019-01-22 14:36:58 回复(0)
我关于这道题的csdn博客https://blog.csdn.net/richenyunqi/article/details/79562434,写的非常详细哦~~
编辑于 2018-04-28 23:21:50 回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int OPEN_TIME = 8*60*60,END_TIME = 21*60*60;
struct player{
    int start,timeNeed,serveStart;
    int isVIP,isOut;
    bool operator < (player p) const{
        return start < p.start;
    }
}p[10001];
struct table{
    int isVIP,endTime,se_num;
}t[101];

int main(){
    int n,k,m,tmp,hour,minute,second;;
    vector<int> rq;
    freopen("in/in.txt","r",stdin);
    cin >> n;
    for(int i = 0; i < n; i++){
        scanf("%d:%d:%d %d %d",&hour,&minute,&second,&tmp,&p[i].isVIP);
        p[i].start = 60*60*hour + 60*minute + second;
        p[i].timeNeed = min(tmp,120)*60;
    }
    sort(p,p+n);
    cin >> k >> m;
    for(int i = 0; i < m; i++){
        cin >> tmp;
        t[tmp].isVIP = 1;
    }
    for(int i = 1; i <= k; i++) t[i].endTime = OPEN_TIME;
    for(int head = 0;head < n && p[head].start < END_TIME;){
        int firstEnd = END_TIME, firstEnd_VIP = END_TIME;
        table *pt = NULL;
        for(int i = 1; i <= k; i++){
            if(t[i].endTime < firstEnd){
                firstEnd = t[i].endTime;
                pt = t+i;
            }
            if(t[i].isVIP && t[i].endTime < firstEnd_VIP){
                firstEnd_VIP = t[i].endTime;
            }
        }
        if(firstEnd >= END_TIME) break;
        int ppp = head;
        bool waitflag = false;
        if(firstEnd > p[ppp].start) waitflag = true;
        if(waitflag && firstEnd_VIP == firstEnd){
            for(int j = head; j < n && p[j].start <= firstEnd; j ++){
                if(p[j].isVIP && !p[j].isOut){
                    ppp = j;
                    break;
                }
            }
        }else{
            bool findVipTable = false;
            if(p[ppp].isVIP){
                for(int i = 1; i <= k; i++){
                    if(t[i].isVIP && t[i].endTime <= p[ppp].start){
                        pt = t+i;
                        findVipTable = true;
                        break;
                    }
                }
            }
            if(!findVipTable){
                for(int i = 1; i <= k; i++){
                    if(t[i].endTime <= p[ppp].start){
                        pt = t+i;
                        break;
                    }
                }
            }
        }
        p[ppp].serveStart = max(p[ppp].start,(*pt).endTime);
        (*pt).endTime = p[ppp].serveStart + p[ppp].timeNeed;
        (*pt).se_num ++;
        p[ppp].isOut = 1;
        rq.push_back(ppp);
        while(p[head].isOut) head++;
    }
    for(int i = 0; i < rq.size(); i++){
        int st = p[rq[i]].start,est = p[rq[i]].serveStart;
            printf("%02d:%02d:%02d %02d:%02d:%02d %d\n",st/3600,st%3600/60,st%60,est/3600,est%3600/60,est%60,(int)((est-st+30)/60));
    }
    for(int i = 1; i <= k-1; i++){
        printf("%d ",t[i].se_num);
    }
    printf("%d\n",t[k].se_num);
    return 0;
}
发表于 2018-02-23 21:28:52 回复(0)