寒假第三讲

一.priority queue

1.对应思路

题目要求实现一个优先队列，支持插入操作 insert(k) 和提取最大元素操作 extractMax。在 C++ 中，我们可以使用 priority_queue 来实现这一结构。priority_queue 默认是最大堆，插入操作将元素添加到堆中，而提取操作返回并删除堆顶的元素。

首先，输入包含多个操作，每个操作可能是 insert k（插入整数 k）、extract（提取最大元素）或 end（结束输入）。对于每个 insert k 操作，我们将元素插入到优先队列中。对于每个 extract 操作，我们从堆中提取并输出当前最大值。

C++ 的 priority_queue 数据结构默认按降序排列（即最大堆），因此无需额外处理即可满足题目要求。程序通过循环读取操作，针对 insert 进行堆插入，针对 extract 进行堆顶元素提取并输出，直到遇到 end 操作停止。

2.代码

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
#include <iostream>
#include <queue>
#include <string>
#include <sstream>

using namespace std;

struct Compare {
    bool operator()(int a, int b) {
        return a < b;
    }
};

int main() {
    priority_queue<int, vector<int>, Compare> pq; 
    string line;

    while (getline(cin, line)) {
        if (line.empty()) continue;

        stringstream ss(line);
        string command;
        ss >> command;

        if (command == "insert") {
            int k;
            ss >> k;
            pq.push(k);
        } else if (command == "extract") {
            if (!pq.empty()) {
                cout << pq.top() << endl; 
                pq.pop(); 
            }
        } else if (command == "end") {
            break;
        }
    }

    return 0;
}

3.学习总结

通过实现这个优先队列，了解了 C++ 中 priority_queue 的基本使用方法。priority_queue 使用最大堆结构，自动保证每次提取的都是当前最大元素，因此插入和提取操作的时间复杂度为 O(log n)，非常高效。此外，使用 priority_queue 还可以避免手动维护堆结构，从而减少了程序复杂度。通过输入和输出流的处理，我也更深入地理解了如何高效处理大规模数据输入。特别是对于题目中限制的 200 万次操作，我们需要确保程序的输入输出效率，因此应该尽量减少不必要的操作，使用合适的输入输出方法提高程序性能。

ST表&&RMQ问题

1.对应思路

该程序利用 ST 表进行静态区间最大值查询。首先，使用 preprocess 函数构建 ST 表，预处理时间复杂度为 O(N log N)。
对于每个查询，我们利用对数表 log_table 预计算查询范围的最优分块，使得查询复杂度降为 O(1)。
通过 read() 进行高效输入，减少 IO 时间，适用于大数据量场景。

2.代码

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
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;

const int MAX_N = 100000;
const int LOG = 17;
int st[MAX_N][LOG];
int log_table[MAX_N + 1];

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

void preprocess(const vector<int>& arr, int n) {
    for (int i = 0; i < n; i++) {
        st[i][0] = arr[i];
    }
    for (int j = 1; (1 << j) <= n; j++) {
        for (int i = 0; i + (1 << j) - 1 < n; i++) {
            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
        }
    }
    log_table[1] = 0;
    for (int i = 2; i <= n; i++) {
        log_table[i] = log_table[i / 2] + 1;
    }
}

int query(int l, int r) {
    int j = log_table[r - l + 1];
    return max(st[l][j], st[r - (1 << j) + 1][j]);
}

int main() {
    int n = read(), m = read();
    vector<int> arr(n);
    for (int i = 0; i < n; i++) {
        arr[i] = read();
    }
    preprocess(arr, n);
    while (m--) {
        int l = read() - 1, r = read() - 1;
        printf("%d\n", query(l, r));
    }
    return 0;
}

3.学习总结

  1. ST 表适用于静态查询，预处理代价较高，但查询极快。
  2. 利用 log_table 预计算对数值可以减少 log 函数调用，提高查询效率。
  3. 快速输入 read() 可有效减少时间开销，适用于高强度数据。
  4. ST 表的核心思想是利用区间的重叠性，通过 dp 方式高效存储区间信息

合并果子

1.对应思路

本题可以通过哈夫曼树（Huffman Tree）的思想来解决，使用最小堆（优先队列）进行贪心合并。
每次取出当前最小的两堆果子进行合并，合并的代价是两者之和，并将新堆重新加入优先队列。
这个过程持续 n-1 次，最终优先队列中只剩下一堆，累加所有合并的代价，即为最小的体力耗费。
由于使用了最小堆，每次插入与删除的复杂度是 O(log n)，整体复杂度为 O(n log n)。

2.代码

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
#include <iostream>
#include <queue>
using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

int main() {
    int n = read();
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < n; i++) {
        pq.push(read());
    }
    int total_cost = 0;
    while (pq.size() > 1) {
        int a = pq.top(); pq.pop();
        int b = pq.top(); pq.pop();
        int cost = a + b;
        total_cost += cost;
        pq.push(cost);
    }
    printf("%d\n", total_cost);
    return 0;
}

3.学习总结

  1. 本题是典型的贪心算法应用，通过局部最优（每次合并最小的两堆）达到全局最优。
  2. 最小堆（优先队列）是一种有效的数据结构，适用于处理动态集合中的最小值问题。
  3. 哈夫曼树的构造与本题类似，它用于最优前缀编码问题，具有广泛应用。
  4. 由于 n 最大为 10000，使用 O(n log n) 复杂度的方法是合理可行的，若用 O(n^2) 的方法会超时。
  5. 通过 priority_queue 的 greater<int> 实现最小堆，提高代码可读性和效率。

四.约瑟夫问题

1.对应思路

该题是经典的约瑟夫环问题。我们通过模拟报数过程来解决，使用双端队列（deque）来模拟每次出圈的操作。首先将所有人的编号依次加入队列，每次将前 mmm 个人报数，第 mmm 个人出列，再从下一个人开始继续报数。该过程重复直到所有人都出列。通过队列的 push_back 和 pop_front 操作来模拟循环报数，保证每个出圈人的编号按顺序输出。

2.代码

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
#include <iostream>
#include <deque>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    deque<int> people;
    
    
    for (int i = 1; i <= n; i++) {
        people.push_back(i);
    }

    
    while (!people.empty()) {
        
        for (int i = 1; i < m; i++) {
            people.push_back(people.front());
            people.pop_front();
        }
      
        cout << people.front() << " ";
        people.pop_front();
    }

    return 0;
}

学习总结

约瑟夫环问题：是经典的动态结构问题，使用队列模拟能够有效解决。

队列操作：队列的 push_back 和 pop_front 操作时间复杂度为 O(1)，适合进行循环模拟。

循环过程理解：通过理解每次从队列中移除第 mmm 个人，并将下一个人重新从头开始报数，可以轻松解决问题。

时间复杂度：对于 n 和 m 较小的情况，O(n * m) 的时间复杂度是可行的。

应用范围：这种方法适用于类似的循环排列问题，理解其实现方式对于解决其他类似问题非常有帮助。

五.Look Up S

1.对应思路

本题的核心在于查找每个奶牛的右侧第一个比她高的奶牛。通过使用栈（stack）数据结构，可以高效地维护一个递减的序列。每次遇到一个奶牛时，将其与栈顶的奶牛进行比较，如果栈顶奶牛的身高不大于当前奶牛，就将其弹出，直到栈顶奶牛的身高大于当前奶牛或栈为空。此时栈顶元素即为当前奶牛的仰望对象。

2.代码

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
#include <iostream>
#include <vector>
using namespace std;

const int MAXN = 1e5 + 5;
int h[MAXN];
int ans[MAXN];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> h[i];
    }
    vector<int> stk;
    for (int i = n; i >= 1; --i) {
        while (!stk.empty() && h[stk.back()] <= h[i]) {
            stk.pop_back();
        }
        ans[i] = stk.empty() ? 0 : stk.back();
        stk.push_back(i);
    }
    for (int i = 1; i <= n; ++i) {
        cout << ans[i] << endl;
    }
    return 0;
}

3.学习总结

栈的应用：本题运用了栈来解决查找“右侧第一个更大元素”的问题。栈非常适合解决递增/递减问题，能够避免不必要的重复计算。

时间复杂度优化：通过栈的方式，每个奶牛的身高最多入栈和出栈一次，整体时间复杂度为 O(N)，满足大规模数据的需求。

贪心策略：栈的使用体现了贪心策略，通过逐步找出最优解。每次都保证栈中的奶牛按递减顺序排列，能快速找到每个奶牛的第一个仰望对象。

解决类似问题：掌握栈的应用可以解决许多类似的“寻找下一个更大/小元素”类型的问题。

五.国旗计划

1.对应思路

  1. 区间转化：

    • 每个边防战士常驻两个边防站 C_i 和 D_i，其奔袭区间为从 C_i 到 D_i。如果 C_i > D_i，说明该区间跨越了边境，需要加上边境的总长度 M，这样就能确保所有区间都是线性区间，方便后续处理。

    排序：

    • 由于区间覆盖问题通常需要按顺序处理，所有边防战士的奔袭区间按照左端点 l 排序。排序后的数组使得我们可以方便地逐一处理每个边防战士，并计算出最少需要多少战士来覆盖边境。

    动态规划和跳跃法：

    • 采用动态规划来解决每个边防战士覆盖的最远区间问题。通过二分查找，找到每个战士能覆盖的最远位置，记录在二维数组 go 中。go[i][0] 存储战士 i 覆盖区间的最远战士 k 的下标。为了更高效地查询最大覆盖，代码通过多级跳跃的方式，构建了 go 数组，并通过动态规划实现快速查询。

    查询最小战士数量：

    • 在查询每个战士必须参与的前提下，我们从该战士的起始位置开始，依次找到能够覆盖区间的最远战士，通过二分查找的方式迭代跳跃，最后计算出最少需要的战士数量。

    输出结果：

    • 对于每个战士，输出必须参与的前提下，最少需要多少个战士来覆盖整个边境线。

2.代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
using namespace std;
int n, m, res[200005];
struct soldier {
	int id, l, r;
} s[400005];
int cmp(soldier a, soldier b)
{
	return a.l < b.l; 
}

int go[400005][20];

void pre()
{
	for(int i = 1, p = i; i <= 2 * n; i++) {
		while(p <= 2 * n && s[p].l <= s[i].r)
			p++;
		int pos = p - 1;
		go[i][0] = pos;
	}
	for(int i = 1; i < 20; i++) {
		for(int j = 1; j <= 2 * n; j++) {
			go[j][i] = go[go[j][i - 1]][i - 1];
		}
	}
}
void search(int k)
{
	int lmt = s[k].l + m, ans = 1, p = k;
	for(int i = 19; i >= 0; i--) {
		if(go[k][i] != 0 && s[go[k][i]].r < lmt) {
			ans += (1 << i);
			k = go[k][i];
		}
	}
	res[s[p].id] = ans + 1;
}
int main()
{
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> s[i].l >> s[i].r;
		if(s[i].r < s[i].l)
			s[i].r += m;
		s[i].id = i;
	}
	sort(s + 1, s + 1 + n, cmp);
	for(int i = 1; i <= n; i++) {
		s[i + n] = s[i];
		s[i + n].l = s[i].l + m;
		s[i + n].r = s[i].r + m;
	}
	pre();
	for(int i = 1; i <= n; i++)
		search(i);
	for(int i = 1; i <= n; i++)
		cout << res[i] << " ";
	return 0;
}

学习总结

这段代码实现了一个经典的区间覆盖问题，核心思想是通过排序和动态规划来高效地解决覆盖区间的最小边防战士数量。具体做法是将所有的区间转化成线性区间，使用排序保证覆盖的顺序性，再通过二分查找和动态规划的结合，优化查询效率。这个思路对于解决类似的区间覆盖问题非常有效，尤其是在大规模数据输入时，能够显著减少计算复杂度。通过合理使用跳跃表和二分查找，代码实现了较高的效率，是学习算法设计和优化的重要案例。