请用顺序队列或链式队列来完成本题。
我们大多都有在银行排队的经历，唉，那坑爹的排队啊！现在就让我们来算算我们这些客户平均需要等多久吧。
每天刚开始时银行会开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
#include<bits/stdc++.h> using namespace std; int m,tot,a,b;//全局变量 template<class T> class Pque{ protected: struct node{ T data; node* next; node():next(NULL){}//以及这里 node.next初始化为NULL 函数体内没有内容 }; node* head; int Size; //protected类型的内容就是一个结构体指针和一个size public: Pque():Size(0){//构造函数 在这里Size初始化为0 head=new node;//构造函数 head申请了新的节点 } ~Pque(){ head=head->next; while(head) { node* t=head; head=head->next; delete t; } } void push(T t){//插入元素是尾插 node* p=head; for(;p->next&&p->next->data<t;p=p->next); //最最一开始这个for语句也是不执行的，因为head->next=NULL,直接新建node*n //这句话还挺重要的哈 //这里不涉及插队哈 大家过来的，都是从底下t=a+b都是等了的，只是等到你了办完工的时间比隔壁也是等了办完公的时间要早， //所以走的早啊 这是正常的 来得早等了一会办了一个小时 来的稍稍晚，等了一会，办一分钟就完，肯定后者要早出对 //完全不涉及插队 node* n=new node; n->data=t;n->next=p->next;p->next=n;//这个data存储的t是办完一个顾客的业务的时间，就比如你0时开门，8分到，办一分钟，data=9 ++Size;//！！！！！！！！！！！！！！ } T pop(){//队列啊 出队只能是队首元素出队 node* p=head->next; head->next=p->next; T t=p->data; delete p;--Size; return t;//T是int类型的元素了 返回个这 } T front(){return head->next->data;} int size(){return Size;}//用函数是因为size是protected类型的 }; int main(){ while(cin>>m){//m是窗口数 Pque<int> win;//这是一个队列 名字是win cin>>tot;//tot总人数 double wt=0;//waitting time for(int i=0;i<tot;++i){ cin>>a>>b;//a:到达的时间 b:办理所需时间 while(win.size()&&win.front()<=a)win.pop(); //这个的意思就是 如果你来的时候 有顾客并且最快办完业务的顾客的时间在你来到银行之前 //那么出队那个最快办理完业务的 这是个while语句 看看能出队几个人 这个语句是把所有早的顾客出队完 //之后根据银行剩余顾客情况 1.银行内顾客数<窗口数 直接进栈办理业务 2.窗口还是满的，剩下的打头的顾客走的时间都比你到的时间晚，那就等，执行else语句 if(win.size()<m) win.push(a+b); //最最一开始执行的是这 因为size=0并且head=new head->next=NULL的 所以进栈 //在顾客数<窗口处的时候 永远是先执行这个if语句不执行上面的for循环 //这个size其实就现在办公的顾客人数push进去一个 size++ pop出去一个 size-- else{ int k=win.front();//前一个最快(!!!因为是head->next->data)办完工的时间 wt+=k-a;//你来的早 就得等 win.pop();//它出栈 队首出栈 win.push(k+b);//在k的基础上+b==你办完工的时间 这个时间入栈 } } cout<<fixed<<setprecision(2)<<wt/tot<<endl; } }
orrrrrrrrrrrrrrrrrrrrrrrrrr
可以先看下面的 理下思路
#include<iostream> #include<iomanip> #include<cmath> #include<cstring> #include<stdio.h> #include<malloc.h> using namespace std; int main() { int m, t; while (cin >> m >> t) { //m:办理业务的银行窗口数 t:整个过程办理业务的人数 这一个while循环完 求出了在一个情形下的情况 int a, b; //a:每一个客户到来的时间 b:该客户办理业务的时间 int sum = 0;//办理业务等待时间 int q[20];//窗口数 上限20个 memset(q,0,sizeof(q));//把该数组所有值先置为0 for (int i = 0; i < t; i++) {//t客人的数量 cin >> a >> b; int cur = 0;//这个代表窗口 要去选出哪个窗口办理完上一个业务最快 int min = q[0];//// for (int i = 0; i < m; i++) { if (q[i] <min) { min = q[i]; cur = i; } }////从min到这 是找出这几个窗口最小的时间 下一个客户到哪个窗口去办理业务 if (a < q[cur]) { //如果a:到达的时间 比所有的办理业务结束的时间还要小 那么它就得等 sum就要++了 sum += (q[cur] - a);//q[cur]:最早结束业务的窗口(eg:24) a:到来的时间(eg:19) 那么就得等24-19=5分钟; q[cur] += b;//那么这个窗口就又添了一个新业务(在这个窗口等肯定就要在这办啊) 所以这个窗口结束业务的时间就要再加 +b[上一个人走 //新客户立马办 不用加排队的时间哇] } else { //如果a:到达的时间 比这个q[cur]()小，就是说现在有空余的窗口 那么就直接在这办理业务了 q[cur] = a + b;//那么这个空余的窗口就有了新业务 结束业务的时间:a+b(假设上一个人办完业务是5分走的 8分来了新客人 办理业务3分钟 //所以这个窗口结束业务的时间8+3=11分钟) } } printf("%.2f ", sum*1.0/t);//算完啦输出 } return 0; }