1017. Queueing at Bank (25)

8.2

#include <cstdio>#include <iostream>#include <algorithm>using namespace std;#define INF 0x7fffffffstruct node{    int st;    int cos;}sttime[10001];bool cmp(node a,node b) {    return a.st < b.st;}int window[101];int n,k;int a,b,c,d;int main() {    cin >> n >> k;    //输入数据，然后求a,b,c的平均值赋值给sttime[i].st;    int cnt = 0;    int ans = 0;//等待的总时间    for (int i = 0; i < n; i++) {        scanf("%d:%d:%d",&a,&b,&c);        scanf("%d",&d);        int k = (a*3600 + b*60 + c);        if (k < 17*3600) {            sttime[cnt].st = k;            sttime[cnt].cos = d;            cnt++;        }    }    //按sttime[i]开始的时间先后排序，然后把最开始的m个存储到m个窗口中    sort(sttime,sttime+cnt,cmp);     //对于每个窗口，初始值赋值为8:00;也就是8*3600    for (int i = 0; i < k; i++) {        window[i] = 8*3600;    }    //修改每个在8点前的customer都修改为8点,并且计算等待的时间    for (int i = 0; i < cnt; i++) {        if (sttime[i].st < 8*3600) {            ans += (8*3600-sttime[i].st);            sttime[i].st = 8*3600;        }    }    //然后开始计算剩余的coustomer的等待时间    //又因为sttime[]已经是从小到大的。    //所以先遍历i,在对于每个i遍历j。    //如果当前的窗口有空余，也就是window[j] <= sttime[i].st,则更新window[j];    for (int i = 0; i < cnt;) {        int found = 0;//能否找到可用的窗口        int dd;        for (int j = 0; j < k; j++) {            if (window[j] <= sttime[i].st) {                //因为题目说：                //It is assumed that no window can be occupied by a single customer for more than 1 hour.                found = 1;//表示找到可用的空的窗口                dd = j;                break;            }        }        if (found == 1) {            window[dd] = sttime[i].st + sttime[i].cos*60;            i++;        }        else {//如果当前顾客i找不到可用的窗口就等待,找到最早结束的时间点。            int minx = INF;            for (int j = 0; j < k; j++) {                if (minx > window[j]) minx = window[j];            }            //找到了,计算当顾客i需要等待的时间            ans += (minx - sttime[i].st);            //更新当前顾客i的信息，用于i++，那一段计算于更新窗口信息            sttime[i].st = minx;        }    }    if (cnt == 0) printf("0.0/n");    else printf("%.1f/n",1.0*ans/cnt/60);    return 0;}