美文网首页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