ACM寒假第三讲

一、Priority Queue

设计思路

题目要求对于一个队列，我们可以执行insert（S，k）即元素插入操作，以及extractMax（S）即移除并返回具有最大键的S元素。这边一开始想到的是构建一个string类型的优先队列，并且针对输入的字符串进行if-else的条件判断（因为执行的操作不多），核心是substr函数的字符检测，在测试途中遇到一个小问题——k也是字符类型，而字符类型的大小比较又偏复杂，于是重新写了一个比较函数，将字符类型k通过roll函数转换为long long类型，之后成功比较。

设计代码

#include <bits/stdc++.h>
using namespace std;

struct Compare {//重写比较函数
	bool operator()(const string &a, const string &b) {
		return stoll(a) < stoll(b);//类型转换
	}
};

int main() {
	priority_queue<string, vector<string>, Compare> q;//优先队列，独立比较方式
	while (1) {
		string s;
		getline(cin, s);//整行输入，避免空格影响
		string word = s.substr(0, 6);
		if (word == "insert") {
			string num = s.substr(7);
			q.push(num);
		} else if (word == "extrac") {
			string num2 = q.top();
			q.pop();
			cout << num2 << endl;
		} else if (s == "end") {
			break;
		}
	}
	return 0;
}

二、ST表&&RMQ问题

设计思路

题目要求设计一个程序，判断静态区间最大值。通过对群里发的PDF以及自己网上查阅资料进行消化，慢慢捋清楚ST表的作用以及应用方法——主要用于重复数据的判断。由于本题的数据时限很短，因此在反复试错之后，通过scanf与printf的输入输出流能达到节省时间的目的，从而通过测试而不需要内置函数read（），至于问题本身也是参考模板进行撰写，这里不多赘述。

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e6+5, MAX_L = 20;
int stmax[MAXN][MAX_L];

int main() {
	int N, M;
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%d", &stmax[i][0]);//输入
	}
	for (int j = 1; j <= log2(N); j++) {
		for (int i = 1; i + (1 << j) - 1 <= N; i++) {
			stmax[i][j] = max(stmax[i][j - 1], stmax[i + (1 << j - 1)][j - 1]);
		}
	}
	while (M--) {
		int l, r;
		scanf("%d%d", &l, &r);
		int x = log2(r - l + 1);//并不需要重新书写log2，本身就是向下取整的，也变相节省了时间
		printf("%d\n", max(stmax[l][x], stmax[r - (1 << x) + 1][x]));
	}
}

三、合并果子

设计思路

题目要算对于n堆果子，求需要消耗的最小体力。此题和2024年数据结构课中的一题《这条拉面好长》类似，算法本质是利用贪心算法进行累加即可；实践到编程中就是利用优先队列构造小根堆，把数据存储之后进行反复的出队累加，再入队的操作，以及来达到最小体力消耗的目的。

设计代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	priority_queue<int, vector<int>, greater<int> > q;
	int l;
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> l;
		q.push(l);
	}
	long long int sum = 0;
	while (1) {
		int u = q.top();
		q.pop();
		int v = q.top();
		q.pop();
		sum = sum + u + v;
		if (q.empty())
			break;
		q.push(u + v);
	}
	cout << sum;
	return 0;
}

四、约瑟夫问题

设计思路

这个题目要求n个人围成一圈，从第一个人开始报数,数到m的人出列，再由下一个人重新从1开始报数，数到m的人再出圈，依次类推，直到所有的人都出圈，请输出依次出圈人的编号。这题就没多想，通过经典的遍历操作就可以做出来，发现竟然没超时，还是很震惊的，毕竟时间复杂度太高了。

附：后续又查阅了网上资料，发现也有暴力破解的代码，也参阅了其他不同的方法，收获颇深。

设计代码

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, m, i, num, j;
	cin >> n >> m;
	vector<int>a(n + 1);
	i = 0;
	num = 0;
	while (num < n) {
		for (j = 1; j <= n; j++)
			if (a[j] == 0) {
				i++;
				if (i % m == 0) {
					cout << j << " ";
					a[j] = 1;//标记。表示已经输出
					num++;
				}
			}
	}
	return 0;
}

五、学习总结

在这次C++代码中，学会了优先队列的使用以及ST表的运用，特别是ST表对于重复性问题的解决，很有启发，目前还在看ST表的相关资料，因为确实还不甚了解。