当前位置:首页 > 题解目录 > 正文内容

【题解】银行排队

亿万年的星光2个月前 (07-04)题解目录260

【题目描述】

我们大多都有在银行排队的经历,唉,那坑爹的排队啊!现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开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

计算过程

客户到达时间处理时间选择窗口窗口空闲时间等待时间
105050
213140
321152
432072

总等待时间 = 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;
}



扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:
返回列表

上一篇:【题解】网线主管

没有最新的文章了...

相关文章

2021年市北区程序设计竞赛题(⼩学组)

最⼤值的相乘(maxx.cpp)【问题描述】第⼀⾏有x个正整数a1,a2,..,ax,第⼆⾏有y个正整数b1,b2,...,by,第三⾏有z个正整数c1,c2,...,cz,假设第⼀⾏的x个正整数中的...

2021年崂山区程序设计竞赛题(初中组)

2021年崂山区程序设计竞赛题(初中组)(比赛时间90分钟,试题满分300分)题目名称区间和区间位数的个数有序数组保存文件sumdigitarray输入文件名sum.indigit.inarray.i...

【题解】建设病房

1.建设病房(build.cpp)【题目描述】2020年1月23日下午,武汉市建设局紧急召集中建三局等单位举行专题会议,要求参照2003年抗击非典期间北京小汤山医院模式,在武汉职工疗养院建设火神山医院...

【题解】数字三角问题

【题解】数字三角问题

【题目描述】给字一个由n行数字组成的数字三角形(等腰三角形)。试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。【输入描述】数字三角形的行数和数字三角形【输出描述】最大的路...

【题解】车辆管理

【题目描述】交通管理局长氓氓现在需要一个管理汽车的系统,每一辆汽车都有许多信息需要去记录。 首先,每一辆汽车都有一个独一无二的车牌号 S,车牌号由 7 个字符组成。 然后,对于每一辆车要记录它的排...

【题解】特殊的质数肋骨

【题目描述】农民约翰母牛总是产生最好的肋骨。你能通过农民约翰和美国农业部标记在每根肋骨上的数字认出它们。农民约翰确定他卖给买方的是真正的质数肋骨,是因为从右边开始切下肋骨,每次还剩下的肋骨上的数字都组...