PAT A1017 Queueing at Bank （25 分）

发布时间：2020-12-14 02:32:40 所属栏目：Windows 来源：网络整理

导读：Suppose a bank has? K?windows open for service. There is a yellow line in front of the windows which devides the waiting area into two parts. All the customers have to wait in line behind the yellow line,until it is his/her turn to be serv

Suppose a bank has?

Now given the arriving time?

Input Specification:

Each input file contains one test case. For each case,the first line contains 2 numbers:?

Notice that the bank opens from 08:00 to 17:00. Anyone arrives early will have to wait in line till 08:00,and anyone comes too late (at or after 17:00:01) will not be served nor counted into the average.

Output Specification:

For each test case,print in one line the average waiting time of all the customers,in minutes and accurate up to 1 decimal place.

Sample Input:

7 3
07:55:00 16
17:00:01 2
07:59:59 15
08:01:00 60
08:00:00 30
08:00:02 2
08:03:00 10

Sample Output:

8.2

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <string.h>
#include <queue>
#include <string>
#include <set>
#include <map>
using namespace std;
const int maxn = 110;
int n,k;
queue<int> q[maxn];
struct person {
    int arr;
    int arr_const;
    int start;
    int pro;
    int wait=0;
};
bool cmp(person p1,person p2) {
    return p1.arr < p2.arr;
}
vector<person> v;
int h,m,s,process;
int main(){
    int count = 0,time = 0;
    cin >> n >> k;
    for (int i = 0; i < n; i++) {
        person p;
        scanf("%d:%d:%d %d",&h,&m,&s,&process);
        getchar();
        time = 3600 * h + 60 * m + s;
        p.arr = time;
        p.start = time;
        p.arr_const = time;
        p.pro = process*60;
        p.wait = 0;
        if (time > 17 * 3600)continue;
        v.push_back(p);
        count++;
    }
    sort(v.begin(),v.end(),cmp);
    int now = 8*3600;
    for (int i = 0; i < count; i++) {
        if (v[i].arr < now) {
            v[i].wait = now - v[i].arr;
            v[i].start = now;
            v[i].arr = now;
        }
    }
    int now_time = 8 * 3600;
    int fast_k = 0;
    for (int i = 0; i < count - k; i++) {
        int fast = 360000;
        for (int j = 0; j < i+k; j++) {
            if (v[j].start + v[j].pro < fast) {
                fast = v[j].start + v[j].pro;
                fast_k = j;
            }
        }
        v[fast_k].start = 360000;
        now_time = fast;
        if (now_time > v[i + k].arr) {
            v[i + k].wait += now_time - v[i + k].arr;
            v[i + k].start = now_time;
        }
    }

    float mean = 0;
    for (int i = 0; i < count; i++) {
        mean += v[i].wait;
    }
    if (count == 0)printf("0.0");
    else {
        mean /= count;
        printf("%.1f",mean/60);
    }
    system("pause");
    return 0;
}

注意点：又是一道逻辑挺简单的题，还是花了1个多小时才ac，前半部分思路是没问题的，后面窗口等待走歪了，一直在顾客上做文章，其实只要把每个窗口的开始服务时间更新，到的比窗口服务时间早的就等待，否则直接开始不用等。

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!