美文网首页PTA甲级
队列模拟 | 1017 Queueing at Bank

队列模拟 | 1017 Queueing at Bank

作者: zilla | 来源:发表于2019-01-27 19:35 被阅读0次

读错题是最惨的。。。以为和1014一样,17:00轮不到就not serve了。。。
然而并不是。。。。。。。。
mdzz看了一个小时看不出有任何错误。。。。
1017 Queueing at Bank

#include <cstdio>
#include <queue>
#include <cstdlib>

using namespace std;
const int OFF = 9 * 60 * 60, INF=0x3f3f3f3f;
struct Customer {
    int t_after8;
    int span_sec;
} customers[10010];

int cmp(const void *c1, const void *c2) {
    return ((Customer *) c1)->t_after8 - ((Customer *) c2)->t_after8;
}

queue<int> windows[100];
int n_cus, k_win;

int main() {
    scanf("%d%d", &n_cus, &k_win);
    int hh, mm, ss, len;
    for (int i = 0; i < n_cus; ++i) {
        scanf("%d:%d:%d%d", &hh, &mm, &ss, &len);
        int t = (hh - 8) * 60 * 60 + mm * 60 + ss;
        if (t > OFF) {
            i--, n_cus--;
            continue;
        }
        customers[i].t_after8 = t;
        customers[i].span_sec = len * 60;
    }
    qsort(customers, n_cus, sizeof(Customer), cmp);
    int wait_tot = 0, z = 0;
    for (; z < n_cus && z < k_win; ++z) {
        if (customers[z].t_after8 < 0) {
            wait_tot += 0 - customers[z].t_after8;
            windows[z].push(customers[z].span_sec);
        } else {
            windows[z].push(customers[z].t_after8 + customers[z].span_sec);
        }
    }
    for (; z < n_cus; ++z) {
        int early = INF, ind = 0;
        for (int i = 0; i < k_win; ++i) {
            if (windows[i].back() < early) {
                early = windows[i].front();
                ind = i;
            }
        }
        windows[ind].pop();
        if (early <= customers[z].t_after8) {
            windows[ind].push(customers[z].t_after8 + customers[z].span_sec);
        } else {
            wait_tot += early - customers[z].t_after8;
            windows[ind].push(early + customers[z].span_sec);
        }
    }
    if(z>0)
        printf("%.1lf\n", wait_tot / 60.0 / z);
    else puts("0.0\n");
    return 0;
}

相关文章

网友评论

    本文标题:队列模拟 | 1017 Queueing at Bank

    本文链接:https://www.haomeiwen.com/subject/ocsnjqtx.html