读错题是最惨的。。。以为和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;
}
网友评论