三元组稀疏矩阵加法

输入格式:

输入第1行为两个同型矩阵的行数m、列数n，矩阵A的非零元素个数t1，矩阵B的非零元素个数t2。
按行优先顺序依次输入矩阵A三元组数据，共t1行，每行3个数，分别表示非零元素的行标、列标和值。
按行优先顺序依次输入矩阵B三元组数据，共t2行，每行3个数，分别表示非零元素的行标、列标和值。

输出格式:

输出第1行为相加后矩阵行数m、列数n及非零元素个数t。
输出t行相加后的三元组顺序表结果，每行输出非零元素的行标、列标和值，每行数据之间用空格分隔。

输入样例1:

1
2
3
4
5
6
7
8
4 4 3 4
0 1 -5
1 3 1
2 2 1
0 1 3
1 3 -1
3 0 5
3 3 7

输出样例1:

1
2
3
4
5
4 4 4
0 1 -2
2 2 1
3 0 5
3 3 7

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<iostream>
using namespace std;
#define MAXDATA 1000
typedef struct
{
	int row;//行
	int col;//列
	int num;//数值
}Node;
struct
{
	int maxRow;//最大行
	int maxCol;//最大列
	int noZero;//非零元素
	Node data[MAXDATA];//数据域
}A,B,AB;//AB为A+B矩阵

int newZero;//A+B时产生的新0

void add()//计算A+B
{
	int i =0, j = 0;
	AB.maxRow = A.maxRow;
	AB.maxCol = A.maxCol;//相加后行列不变
	for (i = 0; i < A.noZero; i++) {
		AB.data[i] = A.data[i];
		AB.noZero++;
	}//先把A拷贝给AB

	for (i = 0; i < B.noZero; i++) {
		for (j = 0; j < AB.noZero; j++) {
			//行列一样直接加
			if (B.data[i].row == AB.data[j].row && B.data[i].col == AB.data[j].col) {
				AB.data[j].num += B.data[i].num;
				if (AB.data[j].num == 0)newZero++;
				break;
			}
		}
		//行列不一样赋值再nozero+1
		if (j == AB.noZero){
			AB.data[AB.noZero] = B.data[i];
			AB.noZero++;
		}
	}
}
void swap(Node& a, Node& b)
{
	Node c = a;
	a = b;
	b = c;
}

void sort()//给AB排个序
{
	for(int i=0;i<AB.noZero-1;i++)
		for (int j = i + 1; j < AB.noZero; j++) {
			if (AB.data[j].row < AB.data[i].row)
				swap(AB.data[j], AB.data[i]);
			else if(AB.data[j].row == AB.data[i].row&& AB.data[j].col < AB.data[i].col)
				swap(AB.data[j], AB.data[i]);
		}
}

int main()
{
	//不用文件操作则在处注释
	freopen("./data2.txt", "r", stdin);

	//初始化矩阵
	//输入矩阵的行和列数
	cin >> A.maxRow >> A.maxCol >> A.noZero >> B.noZero;
	B.maxRow = A.maxRow;
	B.maxCol = A.maxCol;
	//填充数据
	for (int i = 0; i < A.noZero; i++)
		cin >> A.data[i].row >> A.data[i].col >> A.data[i].num;
	for (int i = 0; i < B.noZero; i++)
		cin >> B.data[i].row >> B.data[i].col >> B.data[i].num;
	//相加运算
	add();
	sort();
	printf("%d %d %d\n", AB.maxRow, AB.maxCol, AB.noZero-newZero);
	for (int i = 0; i < AB.noZero; i++)
		if(AB.data[i].num)//不为0再打印
		printf("%d %d %d\n",AB.data[i].row, AB.data[i].col, AB.data[i].num);

}

栈

堆栈是一种经典的后进先出的线性结构，相关的操作主要有“入栈”（在堆栈顶插入一个元素）和“出栈”（将栈顶元素返回并从堆栈中删除）。本题要求你实现另一个附加的操作：“取中值”——即返回所有堆栈中元素键值的中值。给定 N 个元素，如果 N 是偶数，则中值定义为第 N/2 小元；若是奇数，则为第 (N+1)/2 小元。

输入格式：

输入的第一行是正整数 N（≤105）。随后 N 行，每行给出一句指令，为以下 3 种之一：

Push key

Pop

PeekMedian

其中 key 是不超过 105 的正整数；Push 表示“入栈”；Pop 表示“出栈”；PeekMedian 表示“取中值”。

输出格式：

对每个 Push 操作，将 key 插入堆栈，无需输出；对每个 Pop 或 PeekMedian 操作，在一行中输出相应的返回值。若操作非法，则对应输出 Invalid。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
17
Pop
PeekMedian
Push 3
PeekMedian
Push 2
PeekMedian
Push 1
PeekMedian
Pop
Pop
Push 5
Push 4
PeekMedian
Pop
Pop
Pop
Pop

输出样例：

1
2
3
4
5
6
7
8
9
10
11
12
Invalid
Invalid
3
2
2
1
2
5
4
5
3
Invalid

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include<iostream>
using namespace std;
#include<string.h>

struct
{
	int* top;//栈顶
	int* base;//栈底
	int stackSize;//总大小
	int count;//当前大小
}stack;

void init()//初始化栈
{
	stack.base = (int*)malloc(sizeof(int) * stack.stackSize);
	stack.top = stack.base;
}
void push(char *command)//入栈
{
	if (stack.count == stack.stackSize) {//判断是否满
		stack.base = (int*)realloc(stack.base, (stack.stackSize + 100));//重新分配内存
		stack.stackSize = stack.stackSize + 100;//更新栈大小
		stack.top = stack.base + stack.stackSize;//更新栈顶指针
	}
	int num = atoi(&command[5]);//提取出push后的数字
	*(stack.top) = num;
	stack.top++;
	stack.count++;//栈大小增加

}

void pop()//出栈
{
	if (stack.base == stack.top) {
		puts("Invalid");
		return;
	}
	stack.count--;
	stack.top--;//栈大小减少
	cout << *(stack.top) << endl;
	
}

void peekMedian()
{
	if (stack.base == stack.top) {
		puts("Invalid");
		return;
	}
	cout << *(stack.base + (stack.count) / 2) << endl;
}

int main()
{
	//不用文件操作则注释掉
	freopen("./data1.txt", "r", stdin);

	char command[100][15];
	int n;
	stack.stackSize = 100;//栈大小
	init();//初始化栈

	cin >> n;
	getchar();//读掉回车
	for (int i = 0; i < n; i++)//输入命令
		cin.getline(command[i],15);

	for (int i = 0; i < n; i++) {
		//处理命令
		if (!strncmp(command[i], "Pop", 3) || !strncmp(command[i], "pop", 3))pop();
		else if (!strncmp(command[i], "Push", 4) || !strncmp(command[i], "push", 4))push(command[i]);
		else if (!strncmp(command[i], "PeekMedian", 10) || !strncmp(command[i], "peekmedian", 10))peekMedian();
		else puts("指令错误");
	}
}

队列

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

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

输入格式:

输入第1行给出正整数N（≤1000），为顾客总人数；随后N行，每行给出一位顾客的到达时间T和事务处理时间P，并且假设输入数据已经按到达时间先后排好了顺序；最后一行给出正整数K（≤10），为开设的营业窗口数。这里假设每位顾客事务被处理的最长时间为60分钟。

输出格式:

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

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

输入样例：

1
2
3
4
5
6
7
8
9
10
11
9
0 20
1 15
1 61
2 10
10 5
10 3
30 18
31 25
31 2
3

输出样例：

1
2
6.2 17 61
5 3 1

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#include<iostream>
using namespace std;

double aveTime;//平均等待时间
int maxTime;//最大等待时间
int curTime = 0;//当前时间
int n, k;//客人数量，前台数量
int inUse;//正在使用的前台数量

//银行前台
struct bank
{
	int leaveTime;//客人离开时间，为0则代表此处空闲
	int count;//记录处理完多少客人
}rec[10];

//客人
struct guest
{
	int arr;//到达时间
	int deal;//处理时间
	int wait;//等待时间
}gue[1000];

//等待队列
struct queue
{
	struct guest** q;//排队客人
	int head;//队头
	int end;//队尾
	int count;//队伍长度
}que;

void init()//初始化队列
{
	que.q = (struct guest**)malloc(sizeof(struct guest*) * n);
	que.head = 0;
	que.end = 0;
	que.count = 0;
}
void push(int i)//入队 i表示第i个客户已到达
{
	if (que.head == que.end && que.count != 0) {
		return;
	}
	else {//到达后开始排队
		que.q[que.end] = &gue[i];
		que.end = (que.end + 1) % n;
		que.count++;
	}
}
void pop(int i)//出队 i表示第i个银行柜台为空
{
	if (que.head == que.end && que.count == 0) {//为空直接返回
		return;
	}
	else {//出队的客人进入银行柜台
		rec[i].leaveTime = (*que.q[que.head]).deal + curTime;//记录客人将要离开的时间
		rec[i].count++;
		que.head = (que.head + 1) % n;
		que.count--;
		inUse++;
	}
}

int main()
{
	//不用文件操作则注释掉
	freopen("./data2.txt", "r", stdin);

	//输入数据
	cin >> n;
	init();
	for (int i = 0; i < n; i++) {
		cin >> gue[i].arr >> gue[i].deal;
		gue[i].wait = 0;
		if (gue[i].deal > 60)gue[i].deal = 60;//最长处理时间为60	
	}
	cin >> k;


	int cur = 0;//记录正在处理第几个客人
	while (cur != n || inUse != 0) {//所有人都到，并且所有柜台为空，则停止计时
		while (gue[cur].arr <= curTime && cur < n) {//当前时间来了的客人进队	
			push(cur);//排队
			cur++;
		}
		for (int i = 0; i < k; i++)//遍历所有柜台，检查当前时间是否有客人处理完
			if (curTime >= rec[i].leaveTime) {
				if (rec[i].leaveTime) {
					rec[i].leaveTime = 0;
					inUse--;
				}
				pop(i);//出队
			}
		for (int i = 0; i < que.count; i++)
			(*que.q[(i + que.head) % n]).wait++;//等待时间增加
		curTime++;//时间流动

	}
	curTime--;//在这里减去多出来这一分钟


	//输出结果
	for (int i = 0; i < n; i++) {
		aveTime += gue[i].wait;
		if (maxTime < gue[i].wait)maxTime = gue[i].wait;
	}
	aveTime = aveTime / n;
	printf("%.1lf %d %d\n", aveTime, maxTime, curTime);
	for (int i = 0; i < k; i++)printf("%d ", rec[i].count);
	cout << endl;
}