UVa 12657: Boxes in a Line 双向链表

2023-03-12 08:01| 来源: 网络整理| 查看: 265

这道题经历了 2 个小时的 Time limit exceeded (TLE)，终于做完了。

解题思路：双向链表，来执行所有的四个操作。

这道题看似简单，但是有很多坑。

进行操作 3，也就是交换操作的时候，其实有三种情况，两个是 X，Y 相邻，X 可能在左边，也可能在右边。一个是 X 和 Y 不相邻进行操作 4，我一开始用的 swap 函数去交换双向链表中分别记录“之前”和“之后”的指针数组。但是一直 TLE。我以为 swap 交换数组是交换指针，并不会进行一一复制交换。但是事实好像是 C++ 会对他们进行一一复制交换。具体可以看这位同学的分析：C++中swap两个数组逐一交换元素而非交换指针的问题分析

另外，上面那篇分析 C++ swap 的文章里面说 Java 交换两个数组是用交换指针的方式，达到 O(1) 复杂度。但是我不太懂 Java，不知道 Java 具体是怎么实现的。

我手动写了个 swap 交换，其实只是交换二维数组的第一维度下标，来达到变相交换两个一维数组的目的，终于解决了 TLE

#include #include #include using namespace std; const int MAXN = 1e5 + 10; int idx[2][MAXN]; int pre, nxt; int n, m; void link(int l, int r) { idx[pre][r] = l; idx[nxt][l] = r; } int main() { #ifdef LOCAL freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif int case_num = 0; while (scanf("%d%d", &n, &m) != EOF) { pre = 0; nxt = 1; for (int i = 0; i

【本文地址】

公司简介

联系我们