CS3334 Data Structures Midterm

A. A+B Problem

给定两个正整数$A$ 和$B$，求$A+B$。
数据范围：$1 \leq A, B \leq 10^{10^5}$

题解：高精度加法。

时间复杂度：$O(\log A + \log B)$

B. Stock Market

给定一个长度为$N$ 的数组$\{a_i\}$，求这个数组绘制的直方图中最大的矩形面积。
数据范围：$1 \leq N \leq 10^5$

样例输入：

1
2

7
6 2 5 4 5 1 6

样例输出：

1

12

样例说明：选择区间$[3, 5]$，矩形宽度为 3，高度为 4，面积为 12。

题解：单调栈。

创建一个栈储存直方图中的矩形，每个矩形用两个参数表示：

• height：矩形的高度，即该范围内的最小值$\min\limits_{i \leq k \leq j} a_k$
• width：矩形的宽度，即该范围的长度$j-i+1$

为了保证所有矩形合法，这是一个单调栈，即栈中的矩形 height 严格递增。

从左到右考虑直方图中的每一个元素：

• 如果$a_i$ 大于栈顶元素的 height，则目前栈内的矩形均合法，并且新增一个更高的矩形 height = a[i], width = 1，将其入栈
• 如果$a_i$ 小于等于栈顶元素的 height，则目前栈内 height 大于等于$a_i$ 的矩形均变为非法。
  • 将他们出栈，计算出栈的矩形的有效面积，更新最大值
  • 考虑一个例子：即将出栈 height1, width1，height2, width2 两个矩形，根据单调栈有 height1 > height2，则矩形 1 的有效面积为 height1 * width1；将矩形 1 的高度压缩到 height2，则两个矩形一样高，可以合并为一个矩形，其面积为 height2 * (width1 + width2)，作为矩形 2 的有效面积。
  • 因此，记录已经出栈的矩形总宽度 totalWidth，则目前矩形的有效面积为 height[i] * (totalWidth + width[i])，更新最大值
  • 最后，将这些出栈矩形的高度全部压缩至 a[i]，则新增一个矩形 height = a[i], width = totalWidth + 1，将其入栈

最后，直方图中的元素已全部考虑完毕，但是栈中可能还有剩余的矩形，按上述第二种情况处理即可。

时间复杂度：$O(N)$ - 每个元素最多被处理两次，一次入栈，一次出栈

对样例进行模拟：

C. The Longest Increasing Subsequence

给定$N$ 个任务，每个任务于$r_i$ 时刻到达，需要$t_i$ 时间完成，优先级为$p_i$（$p_i=0$ 为高优先级，$p_i=1$ 为低优先级）。
CPU 的处理模式为：将任务按照优先级分为两个队列，高优先级队列和低优先级队列，每次从高优先级队列中选择最早到达的任务执行，如果高优先级队列为空，则从低优先级队列中选择最早到达的任务执行。
求每个任务的完成时刻。
数据范围：$1 \leq N \leq 100$

样例输入：

1
2
3
4
5
6
7
8

3
0 4 1
0 2 0
3 4 0
3
0 4 0
0 2 0
3 4 0

样例输出：

1
2

6 2 10
4 6 10

题解：模拟即可。

在每一时刻$t$：

• 将所有$r_i \leq t$ 的任务加入各自对应的队列
• 如果高优先级队列为空，且低优先级队列非空，弹出低优先级队列中最早到达的任务执行
• 如果高优先级队列非空，弹出高优先级队列中最早到达的任务执行
• 如果两者都为空，说明当前时刻没有任务到达，跳到下一个任务到达的时刻

时间复杂度：$O(N^2)$ - 最坏情况下每次都要遍历所有任务

D. Mira - The Dragon Slayer

比 A 更简单的签到题。