CS101 PA3
T2
考虑贪心，对每一个容器，就是在能够容纳的信息里面选择一个能最大化利用容器的。将信息和容器都按照 a 为关键字排序。然后外层循环容器，对于第 i个容器，如果第 j 个信息的 \(a_j\leq A_i\) ，把第 j 个信息放入待选的信息，然后 j++，直到不能放为止。然后从待选的信息的挑选一个最优的信息 ，即满足 \(d \leq D_i\) 的信息中 \(d_k\) 最大的一个信息，然后 ans++，从待选信息中删除该信息。由于满足了 a 从小到大排序，对于待选的信息, \(a_j \leq A_i \leq A_{i+1}\) ，所以后面的每一个容器都是可以从待选信息中选择的。维护待选信息可使用 \(BST\) ，也可以用 multiset, 在 \(\log n\) 时间内查询。总的时间复杂度是 \(O(n\log n)\).
T3
- \(A\geq D\): 也就是说我们需要尽量快的到达 n 点，直接BFS，每个点的遍历顺序一定是保证最快到达的，如果到达该点发现打不过，那么这个点相当于“死了”，不用考虑路过该点了。
- \(A<D\): 首先是如何判断能否到达 n 点。 这个时候我们只需要尽可能多地从占领的区域的相邻的点中，挑选一个
s[y]最小的一个点，如果能打过，那么attack增加，有利于我打更强的，如果连最小的都打不过，那么说明已经无法从占领区域中扩展了，就这样不断扩大占领区域，用优先队列维护相邻的点，直到能扩展到 n 点就说明可以到达（注：不用扩展到全部点）。 假设我们能够到达 n 点，那么和之前类似，如果到达该点发现打不过，那么我们可以加上一个等待时间wait直到能击败该节点为止dis[pre]+1+wait < dis[y]那么更新 y 点，但是这个时候需要用dijkstra来确保始终从距离最小的点更新。之前判断能不能的时候，我们其实已经达到过n，也就是对所有点，wait最多可以是最终的最优解dis[n]，因为最多可以打dis[n]个小怪来补充攻击力，打败当前点wait>=dis[n]的话，也没关系，因为最后松弛操作会把这种情况滤掉