7-5 银行排队问题之单队列多窗口服务

本文主要是介绍7-5 银行排队问题之单队列多窗口服务，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

基本思路为模拟窗口运行，代码基本有注释。

用到了一点17的特性所以得用pta的clang++编译。稍微修改也可以用g++。

#include <iostream>
#include <iomanip>
#include <tuple>
#define INT_MAX 2147483647
#define INT_MIN -2147483648
using namespace std;
size_t NoAvail = 0xff;
struct Window {
    int served = 0; // 已服务人数
    int end_serve = INT_MAX; // 完成当前任务时的时间
    bool busy = 0; // 是否处于空闲状态
    void work(int work_span) { //设置忙碌状态和任务完成时间
        busy = true;
        end_serve = work_span;
    }
    void complete() { //更新窗口状态函数
        if (busy) {
            busy = false;
            this->served++; 
        }
    }
    friend ostream& operator<<(ostream& out, Window & w) { // 特化输出格式为只输出已服务人数
        out << w.served ;
        return out;
    }
};
struct Customer {
    size_t arrive_time; // 到达时间
    size_t serve_time; // 服务所需时间
    bool isVIP;
    bool operator==(Customer& other) { // 没啥用的
        if (other.arrive_time == arrive_time && other.isVIP == isVIP && other.serve_time == serve_time) return true;
        else return false;
    }
    bool operator==(tuple<size_t, size_t, bool> ano) { // 同上
        if (get<0>(ano) == arrive_time && get<1>(ano) == serve_time && get<2>(ano) == isVIP) return true;
        else return false;
    }
};
Window windows[13];
Customer custom[1050];
size_t vipw_idx = 0;
auto dispatch_window(size_t k) { // 分配窗口并检查分配后窗口是否全部忙碌
    size_t i = 0;
    bool allbusy = true; // 只在后续检查中发现有多余的窗口空闲才取false
    //if (VIP) {
    //    if (!windows[vipw_idx].busy) i = vipw_idx; 
    //}
    while (windows[i].busy) { // 寻找第一个空闲窗口
        i++;
        if (i >= k) break;
    }
    for (size_t j = 0; j < k; j++) { //为了后续兼容有VIP的情况索引从0开始,否则可以直接取i+1
        if (j == i) continue;
        if (!windows[j].busy) {
            allbusy = false;
            break;
        }
    }
    return make_pair(i, allbusy); // std::pair 返回值类型由auto自动推导
}
tuple<size_t,size_t,size_t> custom_loop(size_t n,size_t k) {
	size_t served = 0, w_idx, cur_time = 0, custom_idx = 0; // 总服务人数 分配到的窗口在数组中的索引 当前时间 队首顾客在数组中的索引
	size_t sum_time = 0, max_time = 0, wait_cur = 0; // 总等待时间 最长等待时间 当前等待时间
	bool allbusy = false;
    while (served != n) { // 循环条件为服务总人数小于n
		while (custom_idx < n && cur_time >= custom[custom_idx].arrive_time ) { // 只在到达时间小于等于当前时间才进行窗口分配
			tie(w_idx, allbusy) = dispatch_window(k); //分配 使用cxx11::tie方便获取函数返回的pair
            if (w_idx != NoAvail) { // 有空闲
                windows[w_idx].work(cur_time + custom[custom_idx].serve_time); // 设置窗口状态和任务持续时间
                wait_cur = cur_time - custom[custom_idx].arrive_time;  // 通过到达时间和当前时间的差值来获得等待时间
                if (wait_cur > max_time) max_time = wait_cur;
                sum_time += wait_cur;
                custom_idx++;
            }
            else  break; // 无空闲则跳出分配过程
        }
		int min_time = INT_MAX;
        if (allbusy) { // 若所有窗口都处于忙碌,则将时间拨到最快完成任务的窗口的结束时间,进行下一次分配
            for (auto& _ : windows) {
                if (_.busy && _.end_serve < min_time) min_time = _.end_serve;
            }
        }else if(custom_idx < n){ // 如果有空闲窗口,则将时间调至下一位顾客到达时
			min_time = custom[custom_idx].arrive_time;
		}
		else { // 顾客仅剩下正在窗口服务的人,其余人已完成服务,直接将时间调至最后一个任务完成时
            min_time = INT_MIN;
            for (auto& _ : windows) {
                if (_.busy && _.end_serve > min_time) min_time = _.end_serve;
            }
        }
		for (auto& _ : windows) { // 更新调整时间后所有在这段时间内完成任务的窗口的状态,并记录服务人数
            if (_.busy && _.end_serve <= min_time) {
                _.complete();
                served++;
                allbusy = false;
            }
		}
        cur_time = min_time; // time leap
    }
    return { cur_time,max_time,sum_time }; // 返回std::tuple c++元组，编译期泛型多类型容器
}
int main() {
    cin.sync_with_stdio(false); // 解绑cin跟stdio，提高cin效率
    cout.sync_with_stdio(false);

	size_t n, tmp, k;
    cin >> n;
    for (size_t i = 0; i < n; i++) {
        cin >> custom[i].arrive_time >> tmp;
        if (tmp > 60) tmp = 60;
        custom[i].serve_time = tmp;
        //cin >> custom[i].isVIP;
    }
    cin >> k /* >> vipw_idx*/;
    NoAvail = k; 

    auto [Time, Max, Sum] = custom_loop(n, k);  // 获取模拟窗口结果，使用c++17 struct bind
    // 也可以当参数引用传回来，麻烦，所以用了新特性
    // iomanip setprecision 与 fixed 共用设置小数位数
    // 去掉fixed则setprecision控制浮点数的整数位和小数位的总长度
    cout << fixed << setprecision(1) << static_cast<double>(Sum) / n << " "; 
    cout << Max << " ";
    cout << Time << endl;
	for (size_t i = 0; i < k; i++)
    {
        cout << windows[i]; // 调用Window类的特化operator<< 函数输出每个窗口的服务人数
        if (i != k-1) cout << " ";
    }
    cout << endl;
    return 0;
}

这篇关于7-5 银行排队问题之单队列多窗口服务的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！