PAT甲级1017. Queueing at Bank

时间:2022-04-21 11:27:30

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