DS|队列

2023-12-31 11:32:10

题目一:DS队列 -- 银行排队

题目描述:

在银行营业大厅共服务3种客户,类型为A\B\C,大厅分别设置了3个窗口分别服务三种客户,即每个窗口只服务一种客户。现有一批客户来银行办理业务,每个客户都有类型和办理业务时间。每个窗口按照客户到来的顺序进行服务。

输入要求:

第一行输入先输入n表示客户数量

第二行输入每个客户的类型,数据之间用用空格隔开

第三行输入每个客户的办理时间,数据之间用用空格隔开

输出要求:

第一行输出A类客户的平均办理时间

第二行输出B类客户的平均办理时间

第三行输出C类客户的平均办理时间

输入样例:

8
A B C B C A A A
10 20 30 40 50 60 70 80

输出样例:

55
30
40

代码示例:

#include<iostream>
#include<stack>
#include<string>
#include<cstdlib>
#include<cstring>
#include<iomanip>
#include<queue>

using namespace std;

int main(){
	int n, average_time, size;
	cin >> n;
	queue<int> A, B, C;
	queue<char> type;

	int time;
	char ch;

	for (int i = 0; i < n; i++){
		cin >> ch;
		type.push(ch);
	}

	for (int i = 0; i < n; i++){
		cin >> time;
		if (type.front() == 'A') A.push(time);
		else if (type.front() == 'B') B.push(time);
		else C.push(time);
		type.pop();
	}

	average_time = 0, size = A.size();
	for (int i = 0; i < size; i++) {
		average_time += A.front();
		A.pop();
	}
	cout << average_time / size << endl;

	average_time = 0, size = B.size();
	for (int i = 0; i < size; i++) {
		average_time += B.front();
		B.pop();
	}
	cout << average_time / size << endl;

	average_time = 0, size = C.size();
	for (int i = 0; i < size; i++) {
		average_time += C.front();
		C.pop();
	}
	cout << average_time / size << endl;
	return 0;
}

题目二:DS队列 -- 数制转换

题目描述:

对于任意十进制数转换为k进制,包括整数部分和小数部分转换。整数部分采用除k求余法,小数部分采用乘k取整法例如x=19.125,求2进制转换

整数部分19,					小数部分0.125
19 / 2 = 9 … 1				0.125 * 2 = 0.25 … 0
9 / 2 = 4  … 1				0.25 * 2 = 0.5   … 0
4 / 2 = 2  … 0 				0.5 * 2 = 1      … 1
2 / 2 = 1  … 0
1 / 2 = 0  … 1

所以整数部分转为 10011,小数部分转为0.001,合起来为10011.001

提示整数部分可用堆栈,小数部分可用队列实现

输入要求:

第一行输入一个t,表示下面将有t组测试数据。

接下来每行包含两个参数n和k,n表示要转换的数值,可能是非整数;k表示要转换的数制,1<k<=16

输出要求:

对于每一组测试数据,每行输出转换后的结果,结果精度到小数点后3位

输出小数点后几位的代码如下:

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
double r = 123.56789;
cout<<fixed<<setprecision(4)<<r<<endl;?? //输出小数点后4

return 0;
}

输入样例:

2
19.125 2
15.125 16

输出样例:

10011.001
F.200

代码示例:

#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<iomanip>
#include<queue>

using namespace std;

int main(){
	int t;
	cin >> t;
	double n;
	int k;
	stack<int> integer;//整数
	queue<int> decimal;//小数
	while (t--) {
		cin >> n >> k;
		int it = (int)n;
		double dc = n - it;

		while (it) {
			integer.push(it % k);
			it /= k;
		}

		for (int i = 0; i < 3; i++) {//只要小数点后三位
			decimal.push((int)(dc * k));
			dc *= k;
			dc -= (int)dc;
		}

		int size1 = integer.size();
		for (int i = 0; i < size1; i++) {
			if (integer.top() >= 10) {
				char c = 'A' + integer.top() - 10;
				cout << c;
			}
			else cout << integer.top();
			integer.pop();
		}
		cout << ".";
		int size2 = decimal.size();
		if (size2 <= 3) {
			for (int i = 0; i < size2; i++) {
				if (decimal.front() >= 10){
					char c = 'A' + decimal.front() - 10;
					cout << c;
				}
				else cout << decimal.front();
				decimal.pop();
			}
			for (int i = 3 - size2; i > 0; i--) cout << "0";
		}
		else {
			for (int i = 0; i < 3; i++) {
				if (decimal.front() >= 10) {
					char c = 'A' + decimal.front() - 10;
					cout << c;
				}
				else cout << decimal.front();
				decimal.pop();
			}
		}
		cout << endl;
	}
	return 0;
}

题目三:DS队列 --?银行业务简单模拟

题目描述:

设某银行有A、B两个业务窗口,且处理业务的速度不一样,其中A窗口处理速度是B窗口的2倍 —— 即当A窗口每处理完2个顾客时,B窗口处理完1个顾客。给定到达银行的顾客序列,请按业务完成的顺序输出顾客序列。假定不考虑顾客先后到达的时间间隔,并且当不同窗口同时处理完2个顾客时,A窗口顾客优先输出。

输入要求:

输入为一行正整数,其中第1个数字N(≤1000)为顾客总数,后面跟着N位顾客的编号。编号为奇数的顾客需要到A窗口办理业务,为偶数的顾客则去B窗口。数字间以空格分隔。

输出要求:

按业务处理完成的顺序输出顾客的编号。数字间以空格分隔,但最后一个编号后不能有多余的空格。

输入样例:

8 2 1 3 9 4 11 13 15

输出要求:

1 3 2 9 11 4 13 15

代码示例:

#include<iostream>
#include<queue>

using namespace std;

const int N = 1010;

int main(){
	int t;
	cin >> t;
	int size = t;
	queue<int>A, B, sum;//一个总队列,两个窗口
	int num;
	while (t--) {
		cin >> num;
		if (num % 2) A.push(num);
		else B.push(num);
	}

	while (A.size() >= 2 && B.size() >= 1) {
		cout << A.front() << " ";
		A.pop();
		cout << A.front() << " ";
		A.pop();
		cout << B.front() << " ";
		B.pop();
	}

	//如果A的等待不足两个或者B中不足一个,依次遍历A,B队列
	while (A.size()) {
		if (A.size() == 1 && B.size() == 0) cout << A.front();//A只剩1个客户,B不剩客户,则不用输出“ ”
		else cout << A.front() << " ";//如果A还剩两个,则倒数第二个需要后带“ ”
		A.pop();
	}
	while (B.size()) {
		if (B.size() == 1) cout << B.front();B只剩1个客户,则不用输出“ ”
		else cout << B.front() << " ";
		B.pop();
	}
	return 0;
}

题目四:DS队列 --?银行排队问题之单队列多窗口加VIP服务

题目描述:

假设银行有K个窗口提供服务,窗口前设一条黄线,所有顾客按到达时间在黄线后排成一条长龙。当有窗口空闲时,下一位顾客即去该窗口处理事务。当有多个窗口可选择时,假设顾客总是选择编号最小的窗口。

有些银行会给VIP客户以各种优惠服务,例如专门开辟VIP窗口。为了最大限度地利用资源,VIP窗口的服务机制定义为:当队列中没有VIP客户时,该窗口为普通顾客服务;当该窗口空闲并且队列中有VIP客户在等待时,排在最前面的VIP客户享受该窗口的服务。同时,当轮到某VIP客户出列时,若VIP窗口非空,该客户可以选择空闲的普通窗口;否则一定选择VIP窗口。

本题要求输出前来等待服务的N位顾客的平均等待时间、最长等待时间、最后完成时间,并且统计每个窗口服务了多少名顾客。

输入要求:

输入第1行给出正整数N(≤1000),为顾客总人数;随后N行,每行给出一位顾客的到达时间T、事务处理时间P和是否VIP的标志(1是VIP,0则不是),并且假设输入数据已经按到达时间先后排好了顺序;最后一行给出正整数K(≤10)—— 为开设的营业窗口数,以及VIP窗口的编号(从0到K?1)。这里假设每位顾客事务被处理的最长时间为60分钟。

输出要求:

在第一行中输出平均等待时间(输出到小数点后1位)、最长等待时间、最后完成时间,之间用1个空格分隔,行末不能有多余空格。

在第二行中按编号递增顺序输出每个窗口服务了多少名顾客,数字之间用1个空格分隔,行末不能有多余空格。

输入样例:

10
0 20 0
0 20 0
1 68 1
1 12 1
2 15 0
2 10 0
3 15 1
10 12 1
30 15 0
62 5 1
3 1

输出样例:

15.1 35 67
4 5 1

代码示例:

#include<iostream>
#include<cmath>
#include<iomanip>
using namespace std;

const int MAXN = 2000;
const int INF = 0x3f3f3f3f;

struct Banker {
    int T;  // 到达时间
    int P;  // 事务处理时间
    int VIP;  // 是否是VIP
};

Banker queueBank[MAXN];
bool used[MAXN], itime[11][MAXN * 60];
int total_serve[MAXN];

int main() {
    int n;
    cin >> n;

    // 输入每个顾客的到达时间、事务处理时间和VIP状态
    for (int i = 0; i < n; i++) {
        cin >> queueBank[i].T >> queueBank[i].P >> queueBank[i].VIP;
        if (queueBank[i].P > 60) queueBank[i].P = 60;  // 限制事务处理时间不超过60分钟
    }

    int k, v;
    cin >> k >> v;
    int cnt = n, sum_waitime = 0, max_waitime = 0, finish = 0;

    // 模拟银行业务处理过程
    for (int t = 0; cnt; t++) {
        // 处理VIP客户
        if (itime[v][t] == false) {
            for (int i = 0; i < n; i++) {
                if (used[i] || !queueBank[i].VIP) continue;
                if (queueBank[i].T > t) break;
                total_serve[v]++;
                max_waitime = max(max_waitime, t - queueBank[i].T);
                finish = max(finish, t + queueBank[i].P);
                sum_waitime += (t - queueBank[i].T);
                cnt--;
                used[i] = true;
                for (int j = 0; j < queueBank[i].P; j++) itime[v][t + j] = true;
                break;
            }
        }
        // 处理普通客户
        for (int i = 0; i < k; i++) {
            if (itime[i][t] == false) {
                for (int j = 0; j < n; j++) {
                    if (used[j]) continue;
                    if (queueBank[j].T > t) break;
                    total_serve[i]++;
                    max_waitime = max(max_waitime, t - queueBank[j].T);
                    sum_waitime += (t - queueBank[j].T);
                    cnt--;
                    used[j] = true;
                    finish = max(finish, t + queueBank[j].P);
                    for (int h = 0; h < queueBank[j].P; h++) itime[i][t + h] = true;
                    break;
                }
            }
        }
    }

    // 输出结果
    cout << fixed << setprecision(1) << sum_waitime * 1.0 / n << " ";  // 平均等待时间
    cout << max_waitime << " " << finish << endl;  // 最长等待时间和处理结束时间

    for (int i = 0; i < k; i++) {
        if (i) cout << " ";
        cout << total_serve[i];  // 每个窗口的服务客户数量
    }
    return 0;
}

问题五:DS队列 -- 排队游戏

题目描述:

在幼儿园中,老师安排小朋友做一个排队的游戏。首先老师精心的把数目相同的小男孩和小女孩编排在一个队列中,每个小孩按其在队列中的位置发给一个编号(编号从0开始)。然后老师告诉小朋友们,站在前边的小男孩可以和他后边相邻的小女孩手拉手离开队列,剩余的小朋友重新站拢,再按前后相邻的小男孩小女孩手拉手离开队列游戏,如此往复。由于教师精心的安排,恰好可以保证每两个小朋友都能手拉手离开队列,并且最后离开的两个小朋友是编号最小的和最大的两个小朋友。(注:只有小男孩在前,小女孩在后,且他们两之间没有其他的小朋友,他们才能手拉手离开队列)。请根据老师的排队,按小女孩编号从小到大的顺序,给出所有手拉手离开队列的小男孩和小女孩的编号对。

输入要求:

用一个字符串代表小朋友队列。字符串中只会出现两个字符,分别代表小男孩和小女孩,首先出现的字符代表小男孩,另一个字符代表小女孩。小孩总数不超过2000。

输出要求:

按小女孩编号顺序,顺序输出手拉手离开队列的小男孩和小女孩的编号对,每行一对编号,编号之间用一个空格分隔。

输入样例:

((()(())())(()))

输出样例:

2 3
5 6
4 7
8 9
1 10
12 13
11 14
0 15

代码示例:

#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<queue>

using namespace std;

struct group {
	int boy;
	int girl;
};

int main(){
	string str;
	cin >> str;
	int lenth = str.size();
	stack<int> index;
	queue<group> ultimate;
	char boy = str[0];
	index.push(0);
	for (int i = 1; i < lenth; i++) {
		if (str[i] == boy) index.push(i);
		else {
			ultimate.push({ index.top(),i });
			index.pop();
		}
	}

	while (ultimate.size()) {
		cout << ultimate.front().boy << " " << ultimate.front().girl << endl;
		ultimate.pop();
	}
	cout << endl;
	return 0;
}

问题六:DS队列 -- 组队列

题目描述:

组队列是队列结构中一种常见的队列结构,在很多地方有着广泛应用。组队列是是指队列内的元素分组聚集在一起。组队列包含两种命令:

1、 ENQUEUE,表示当有新的元素进入队列,首先会检索是否有同一组的元素已经存在,如果有,则新元素排在同组的最后,如果没有则插入队列末尾。

2、 DEQUEUE,表示队列头元素出队

3、 STOP,停止操作

输入要求:

第1行输入一个t(t<=10),表示1个队列中有多少个组

第2行输入一个第1组的元素个数和数值

第3行输入一个第2组的元素个数和数值

以此类推输入完t组以定义同组元素之后,开始输入多个操作命令(<200),对空的组队列进行操作,例如输入ENQUEUE 100,表示把元素100插入队列

输出要求:

DEQUEUE出队的元素

输入样例:

2
3 101 102 103
3 201 202 203
ENQUEUE 101
ENQUEUE 201
ENQUEUE 102
ENQUEUE 202
ENQUEUE 103
ENQUEUE 203
DEQUEUE
DEQUEUE
DEQUEUE
STOP
3
3 101 102 103
3 201 202 203
3 301 302 303
ENQUEUE 201
ENQUEUE 301
ENQUEUE 102
DEQUEUE
DEQUEUE
DEQUEUE
ENQUEUE 101
ENQUEUE 203
ENQUEUE 302
ENQUEUE 301
DEQUEUE
DEQUEUE
DEQUEUE
STOP

输出样例:

101 102 103
201 301 102 101 203 302

代码示例:

#include<iostream>
#include<stack>
#include<string>
#include<cstring>
#include<iomanip>
#include<queue>
#include<map>

using namespace std;

const int N = 1010;

int main()
{
	map<int, int> maplive;
	int n, t, num;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> t;
		for (int j = 0; j < t; j++) {
			cin >> num;
			maplive[num] = i;
		}
	}

	queue<int> my_queue[11];
	queue<int> out_queue;
	queue<int> markindex;
	bool mark[11] = { 0 };
	string opertion;
	while (1) {
		cin >> opertion;
		if (opertion == "STOP") break;
		else if (opertion == "ENQUEUE") {
			cin >> num;
			my_queue[maplive[num]].push(num);
			if (!mark[maplive[num]]) {
				markindex.push(maplive[num]);
				mark[maplive[num]] = true;
			}
		}
		else
		{
			out_queue.push(my_queue[markindex.front()].front());
			my_queue[markindex.front()].pop();
			if (my_queue[markindex.front()].empty()) {
				mark[markindex.front()] = false;
				markindex.pop();
			}
		}
	}

	while (out_queue.size()) {
		cout << out_queue.front();
		if (out_queue.size() == 1) cout << endl;
		else cout << " ";
		out_queue.pop();
	}
}

文章来源:https://blog.csdn.net/2203_75720729/article/details/135306245
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。