2 u013172314 u013172314 于 2015.05.25 14:45 提问

PAT 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));
}
Csdn user default icon
上传中...
上传图片
插入图片