风一样的年代
2015-05-25 06:45PAT 1017. Queueing at Bank
【题目链接】
这道题比之前的那道要简单,看网上的好多篇博文,他们说的我都注意到了,但是最后一个case始终过不了,求大神解惑,在线等!!!
#include <iostream>
#include <string>
#include <cstdio>
#include <algorithm>
using namespace std;
int n, k;
int leaveTime[10005];
int waitTime[10005];
int window[105]; //存放对应窗口当前服务的客户编号
struct Customer
{
int arriveTime;
int processTime;
}buf[10005];
bool cmp(Customer a, Customer b)
{
return a.arriveTime < b.arriveTime;
}
int main()
{
//freopen("in_1017.txt", "r", stdin);
int hour, minute, second;
cin >> n >> k;
for(int i = 0; i < n; i++)
{
cin >> hour;
getchar();
cin >> minute;
getchar();
cin >> second >> buf[i].processTime;
buf[i].processTime *= 60;
buf[i].arriveTime = hour * 3600 + minute * 60 + second;
}
sort(buf, buf + n, cmp);
int cus;
int num = 0; //在17点之后到达的顾客数量
for(int i = 0; i < k && i < n; i++)
{
cus = i;
window[i] = i;
if(buf[i].arriveTime < 8 * 3600)
{
leaveTime[i] = 8 * 3600 + buf[i].processTime;
waitTime[i] = 8 * 3600 - buf[i].arriveTime;
}
else if(buf[i].arriveTime <= 17 * 3600)
{
leaveTime[i] = buf[i].arriveTime + buf[i].processTime;
waitTime[i] = 0;
}
else
{
waitTime[i] = -1;
num++;
continue;
}
}
int min_leave; //最早的离开时间********************
int min_win; //每次离开的客户对应的窗口序号
for(int i = cus + 1; i < n; i++)
{
if(buf[i].arriveTime > 17 * 3600)
{
waitTime[i] = -1;
num++;
continue;
}
min_leave = 24 * 3600 + 100;
for(int j = 0; j < k; j++)
{
int u = window[j]; //u保存当前窗口服务的客户编号
if(leaveTime[u] < min_leave)
{
min_leave = leaveTime[u];
cus = u;
min_win = j;
}
}
window[min_win] = i;
//当有窗口空闲, 但是下一位顾客还未到来时, 窗口需要等待;
if(leaveTime[cus] < buf[i].arriveTime) leaveTime[cus] = buf[i].arriveTime;
waitTime[i] = leaveTime[cus] - buf[i].arriveTime;
leaveTime[i] = leaveTime[cus] + buf[i].processTime;
}
double average = 0;
for(int i = 0; i < n; i++)
if(waitTime[i] >= 0) average += waitTime[i];
else break;
if(n == num) num = 0; //若全部顾客在17点之后到达,下面语句分母为0
printf("%.1lf\n", average / 60 / (n - num));
}
- 点赞
- 回答
- 收藏
- 复制链接分享
0条回答
为你推荐
- Go- CPU /内存/网络
- windows
- 1个回答
- Golang后台处理
- it技术
- 互联网问答
- IT行业问题
- 计算机技术
- 编程语言问答
- 5个回答
- 我想将Consolibyte PHP QuickBooks库与PDO一起使用
- pdo
- php
- 2个回答
- Omnipay PHPUnit Guzzle httpClient 404错误 - 模拟json
- unit-testing
- php
- 1个回答
- 如何在网页上加载大量php生成的图像
- http-headers
- image
- php
- download
- http
- 1个回答
换一换