PAT A1017

題目：https://pintia.cn/problem-sets/994805342720868352/problems/994805491530579968

氣的爆炸，用的時間按秒增加模拟，結果最後一個用例逾時，已盡力。

#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 10010;
int n, k, flag = 8 * 3600, endtime = 17 * 3600, wait = 0, num = 0;
queue<int> windows[110];
struct customer{
	int t;
	int p;
}c[maxn];
bool cmp(customer a, customer b){
	return a.t < b.t;
}
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++){
		int h, m, s;
		scanf("%d:%d:%d %d", &h, &m, &s, &c[i].p);
		c[i].t = h * 3600 + m * 60 + s;
		if(c[i].t >= endtime){
			i--;
			n--;
			continue;
		}
		if(c[i].p>=60)
			c[i].p = 3600;
		else
			c[i].p *= 60;

	}
	sort(c, c + n, cmp);
	while(flag <= endtime && num < n && c[num].t <= endtime){
		for(int i = 0; i < k; i++){
			if(!windows[i].empty()){
				int q = windows[i].front();
				c[q].p--;
				if(c[q].p == 0){
					windows[i].pop();
				}
			}
		}
		for(int i = num; i < n; i++){
			if(c[i].t > flag)
				break;
			else{
				for(int j = 0; j < k; j++){
					if(windows[j].empty()){
						windows[j].push(i);
						wait += flag - c[i].t;
						num++;
						break;
					}
				}
			}
		}
		flag++;
	}
	if(num){
		printf("%.1f\n", 1.0 * wait / 60 / num);
	}
	else
		printf("0.0");
	return 0;
}
           

換了一種算法，記錄每個視窗的可使用的時間，來人後計算下一次的時間，循環每個人，找最小時間的視窗使用。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 10010;
const int INF = 1e9;
int n, k, st = 8 * 3600, endtime = 17 * 3600, wait = 0;
int windows[110];
struct customer{
	int t;
	int p;
}c[maxn];
bool cmp(customer a, customer b){
	return a.t < b.t;
}
int main(){
	scanf("%d%d", &n, &k);
	for(int i = 0; i < n; i++){
		int h, m, s;
		scanf("%d:%d:%d %d", &h, &m, &s, &c[i].p);
		c[i].t = h * 3600 + m * 60 + s;
		if(c[i].t > endtime){
			i--;
			n--;
			continue;
		}
		if(c[i].p >= 60)
			c[i].p = 3600;
		else
			c[i].p *= 60;

	}
	sort(c, c + n, cmp);
	for(int i = 0; i < k; i++){
		windows[i] = st;
	}
	for(int i = 0; i < n; i++){
		int u = -1, MIN = INF;
		for(int j = 0; j < k; j++){
			if(windows[j] < MIN){
				MIN = windows[j];
				u = j;
			}
		}
		if(u == -1)
			break;
		if(windows[u] >= c[i].t){
			wait += (windows[u] - c[i].t);
			windows[u] += c[i].p;
		}
		else
			windows[u] = c[i].t + c[i].p;
	}
	if(n){
		printf("%.1f\n", wait / 60.0 / n);
	}
	else
		printf("0.0\n");
	return 0;
}
           

題目中要求，你隻要在工作時間内來了，就要開始等，即便你沒有享受到服務。是以在循環每個視窗的時候，我原先為了提高速度加了一個條件，即視窗的可使用時間都大于下班時間，就是錯誤的。