PAT甲级1017. Queueing at Bank

题意：

假设一家银行有K台开放服务。窗前有一条黄线，将等候区分为两部分。所有的客户都必须在黄线后面排队，直到他/她轮到服务，并有一个可用的窗口。

假设一个客户不能占用1个小时以上的窗口。

现在考虑到每个客户的到达时间T和处理时间P，您应该告诉所有客户的平均等待时间。

输入：

每个输入文件包含一个测试用例。对于每种情况，

第一行包含2个数字：N（<= 10000） - 客户总数，K（<= 100） - 窗口数。然后N行跟随，每个包含2次：HH：MM：SS - 到达时间，P - 客户的处理时间（以分钟为单位）。这里HH在[00，23]的范围内，MM和SS都在[00,59]中。

假设没有两个客户同时到达。

请注意，银行营业时间为08:00至17:00。任何人提前到达，必须等到08:00，任何人来得太晚（17:00:01之间或之后）将不会服务也不会计入平均水平。

输出：

对于每个测试用例，

在一行中打印所有客户的平均等待时间，在几分钟内精确到小数点后1位。

思路：

模拟排队。我用的优先队列。跟前面一道题有点像。

注意点：

• 只要在17：00或者17：00前到都可以被服务
• 都在17：00后到达的话，注意0为除数的情况

ac代码：

C++

// pat1017.cpp : 定义控制台应用程序的入口点。

//

#include "stdafx.h"

#include<iostream>

#include<cstdio>

#include<string>

#include<algorithm>

#include<queue>

#include<vector>

#include<cstring>

#include<unordered_map>

#include<iomanip>

using namespace std;

struct custom

{

	double arriving;

	int process;

	double ending;

	int window;

	custom() : arriving(0), process(0), ending(0), window(0) {};

};

vector<custom> cus;

struct mycmp {

	bool operator()(custom& a, custom& b) const

	{

		return a.ending> b.ending;

	}

};

static bool cmp(custom a, custom b)

{

	return a.arriving < b.arriving;

}

double counttime(string a, string b)

{

	double ahour, bhour, aminute, bminute, asecond, bsecond;

	ahour = stoi(a.substr(0, 2));

	aminute = stoi(a.substr(3, 2));

	asecond = stoi(a.substr(6, 2));

	bhour = stoi(b.substr(0, 2));

	bminute = stoi(b.substr(3, 2));

	bsecond = stoi(b.substr(6, 2));

	double res = 0;

	res = (ahour - bhour) * 60 + (aminute - bminute) + (asecond - bsecond) / 60;

	return res;

}

int main()

{

	int n, m;

	string arrive;

	priority_queue<custom, vector<custom>, mycmp> q;

	cin >> n >> m;

	for (int i = 0; i < n; i++)

	{

		custom c;

		cin >> arrive >> c.process;

		c.arriving = counttime(arrive, "08:00:00");

		if (c.process > 60) c.process = 60;

		cus.push_back(c);

	}

	sort(cus.begin(), cus.end(),cmp);

	for (int i = 0; i < m; i++)

	{

		custom c;

		//c.window = i;

		c.ending = 0;

		q.push(c);

	}

	int len = cus.size();

	int pos = 0;

	double wait = 0;

	while (pos < len && cus[pos].arriving <= 540)

	{

		custom t = q.top();

		q.pop();

		//if (t.ending > 540) break;					//只要来了排在队伍就可以被服务

		if (cus[pos].arriving >= t.ending)

		{

			wait += 0;

			cus[pos].ending = cus[pos].arriving + cus[pos].process;

		}

		else

		{

			wait += t.ending - cus[pos].arriving;

			cus[pos].ending = t.ending + cus[pos].process;

		}

		//cus[pos].window = t.window;

		q.push(cus[pos]);

		pos++;

	}

	double res;

	if (pos == 0) res = 0;               //防止所有客户17:00后到，0为除数

	else res = wait / pos;

	cout << fixed << setprecision(1) << res << endl;

	//for (int i = 0; i < cus.size(); i++)

	//	cout << cus[i].arriving << " " << cus[i].process << endl;

    return 0;

}