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;
}