【题目描述】

我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。

每天刚开始时银行会开m个窗口来为我们total个客户办理业务，当有客户需要办理业务时，先选择可以办理业务的窗口，如果有多个窗口可以办理业务就选择空闲时间最长的窗口，如果有多个窗口空闲的时间一样长，则选择序号小的窗口办理业务。假设我们每个人来到的时间和办理业务所需要的时间（为了简化问题，采用整数表示时间）都知道了。现在请你算算我们平均需要等待多久呢？

【输入描述】

有多组测试数据，每组数据开始有两个正整数m(<20)和total(<200)，后面有total对整数，对应客户先后到来的时间以及办理业务所需的时间。

【输出描述】

【样例输入】

2 6 1 3 4 1 5 3 9 2 13 4 13 3  3 14 0 3 2 2 2 4 5 4 7 2 11 3 12 3 12 4 12 1 13 3 15 4 19 1 22 3 23 2  2 5 0 6 0 5 0 6 7 1 7 2

【样例输出】

0.00  0.29  1.20

【题目分析】

1. 贪心策略。客户到达时，选择当前最早空闲的窗口（即该窗口队尾客户的离开时间最早）。

2. 如果客户到达时窗口仍被占用，则需等待（等待时间 = 窗口空闲时间 - 客户到达时间）。

3. 如果客户到达时窗口空闲，则直接开始处理（等待时间 = 0）。

核心算法流程：

int processCustomer(int windows[], Customer customer, int m) {      // 1. 选择最优窗口（当前最早空闲的窗口）      int best = 0;      for (int i = 1; i < m; ++i) {          if (windows[i] < windows[best]) {              best = i;          }      }        // 2. 计算等待时间      int wait_time = 0;      if (customer.arrive_time <= windows[best]) {          // 需要等待          wait_time = windows[best] - customer.arrive_time;          windows[best] += customer.process_time; // 更新窗口时间      } else {          // 无需等待，直接占用窗口          windows[best] = customer.arrive_time + customer.process_time;      }        return wait_time;  }

1. 选择最优窗口：

• 遍历所有窗口，找到 windows[i] 最小的窗口（即最早空闲的窗口）。

2. 计算等待时间：

• 如果客户到达时窗口仍被占用（arrive_time <= windows[best]），则等待时间为 windows[best] - arrive_time。

• 否则，客户无需等待，窗口空闲时间更新为 arrive_time + process_time。

3. 返回当前客户的等待时间。

例子：

输入：

2 4  0 5  1 3  2 1  3 2

计算过程：

总等待时间 = 0 + 0 + 2 + 2 = 4

平均等待时间 = 4 / 4 = 1.00

输出：

1.00

【参考答案】

#include <bits/stdc++.h>  using namespace std;  // 客户数据结构（原C代码的arri/stay变量）  struct Customer {  	int arrive_time;  // 到达时间  	int process_time; // 处理时间  };  Customer customers[1000]; // 客户数组  int windows[20];   // 窗口队列  /**   * 处理单个客户并返回更新后的窗口时间    customer  当前客户数据（值传递）     m     窗口总数   * @return            当前客户的等待时间   */  int processCustomer(Customer customer, int m) {  	int best = 0;  	// 选择最优窗口：队尾离开时间最早的窗口  	for (int i = 1; i < m; ++i) {  		if (windows[i] < windows[best]) {  			best = i;  		}  	}  	int wait_time = 0;  	// 判断是否需要等待  	if (customer.arrive_time <= windows[best]) {  		wait_time = windows[best] - customer.arrive_time;  		windows[best] += customer.process_time; // 更新窗口时间  	} else {  		windows[best] = customer.arrive_time + customer.process_time;  	}  	return wait_time; // 返回当前客户的等待时间  }    int main() {  	int m;  // 窗口数  	int total; // 客户总数  	// 多组测试数据循环  	while (cin >> m >> total) {  		// 初始化窗口时间  		for (int i = 0; i < m; ++i) {  			windows[i] = 0;  		}  		double total_wait = 0.0; // 总等待时间  		// 读取所有客户数据  		for (int i = 0; i < total; ++i) {  			cin >> customers[i].arrive_time >> customers[i].process_time;  		}  		// 处理每个客户并累加等待时间  		for (int i = 0; i < total; ++i) {  			total_wait += processCustomer(customers[i], m);  		}  		// 输出平均等待时间  		printf("%.2lf\n",(total_wait / total) );  	}  	return 0;  }