题解 P5462 【X龙珠】

看了下大佬，似乎都是$\Theta(n)$链表过的？ 没有办法我太弱了，考场上并没有想到这个方法。当时看到一个$n \leq 1e5$，一个最大值，就想用平衡树了。 ~~然而这里并没有平衡树~~ 好吧因为我需要两棵结构体平衡树，嫌麻烦就敲了两个set~~STL大法好~~ 然后常数爆炸，慢的要死。。。 诶，思路？纯模拟吧。。。 贪心策略不用我讲了吧。。。 建两个set，一个把所有元素按数组下标排序，设为S2，一个把所有元素按数值大小排序，设为S1。 然后每次从S1里取出最大值（区间最值），再通过S2找出它的后一个元素（后驱），先后插入到队列里，再删除，就OK了吧。 ~~不会set取最大值？最大值是set的最后一个元素，所以只要让一个iterator等于end再减减就好了~~ 但是康到这里你可能觉得笔者太Naive了。比如这组数据：n = 4， 数组为 1， 2， 3， 4； 那么第一次取出来的值就是4, 而4没有后驱，这个时候就会出错。 ~~辣鸡作者写的什么玩意儿~~ 只要你继续看下去，这个问题会在两分钟内消失。考虑到每次选取（一对数中靠前的那个），只要不是当前序列的最后一个，这次选取就是合法的。 那么我们就有这样的解决方案：每次不把序列的最后一个放到set（平衡树）里，并加入特判。具体来说，对于以下数据： n = 4, arr\[] = {1, 2, 3, 4}; 最开始的时候，我们把除了最后一个元素都放进set， 此时set中的元素（为了方便理解只管一个set）为 {1， 2， 3} 再设个变量t2保存最后元素“4”和值（4） 第一次操作显然取出3。 然后特判：3是不是**set里的**最后一个元素？ 是的。 我们把3 push到队列里， 然后找到3的前驱（下标排序）， 是2。 然后把t2 push到队列里，做完这之后，让t2 = 2，也就是我们刚刚找出的前驱。 最后删除3，第一步操作就完成了。 如果n不变，arr\[] = {4, 3, 2, 1} 第一步取出4， 不是最后一个元素； 直接将4和3依次push到队列里，再把set里面的erase掉，这一步操作就完成了。 单次操作复杂度$\Theta(log_2 n)$, 总复杂度$\Theta(n log_2 n)$。真的慢的要死，还没sort的快。 好了，思路已经讲完了。其实这题如果手敲平衡树的话，对代码实现能力还是有很大帮助的。~~所以你们闲着无聊可以试试~~ 具体看~~几乎不可读的~~代码吧 ```cpp #include <cstdio> #include <iostream> #include <map> #include <set> #include <queue> constexpr int INF = 0x3f3f3f3f; std::queue<int> q; struct Node1{ int index, val; Node1(void) : index(0), val(0) {} Node1(int a, int b) : index(a), val(b) {} bool operator<(const Node1 &a) const{ return this->index < a.index; } }; struct Node2{ int index, val; Node2(void) : index(0), val(0) {} Node2(int a, int b) : index(a), val(b) {} bool operator<(const Node2 &a) const{ return this->val < a.val; } }; std::set<Node1> tts;\\原谅我不羁放纵乱取名 std::set<Node2> sst;\\上面的是按下标排，下面的是按数值排 int n; int main(int argc, char const *argv[]) { int *tmpArray; scanf("%d", &n); tmpArray = new int[n]; for (int i = 0; i != n; ++i) scanf("%d", &tmpArray[i]); for (int i = 0; i != n - 1; ++i) sst.insert(Node2(i, tmpArray[i])), tts.insert(Node1(i, tmpArray[i])); std::set<Node2>::iterator i; std::set<Node1>::iterator j; int endindex, endval; endindex = n - 1, endval = tmpArray[n - 1]; while (!sst.empty()) { i = sst.end(); --i;\\取最值 int index1 = i->index, val1 = i->val; j = tts.find(Node1(index1, val1)); int index2, val2; ++j; if (j == tts.end()) {//是最后一个元素 --j;\\取前驱 index2 = endindex, val2 = endval; if (j != tts.begin()) --j;\\防RE endindex = j->index, endval = j->val; sst.erase(Node2(endindex, endval)), tts.erase(j); } else { index2 = j->index, val2 = j->val; sst.erase(Node2(index2, val2)), tts.erase(Node1(index2, val2)); } sst.erase(Node2(index1, val1)), tts.erase(Node1(index1, val1)); q.emplace(val1), q.emplace(val2); } while (!q.empty()) { printf("%d ", q.front()); q.pop(); } return 0; } ``` 代码里可能含有很多“多此一举”的东西。。。 辣鸡作者滚粗了，有问题评论或私信吧