temp

Algor

2025-11-23 20:55:13

发布于：广东

5阅读

0回复

0点赞

我直接一点说：这份代码的问题可以分成两类：

就算逻辑是对的，也会在大数据上直接炸掉（数组开太小、语法不标准）
逻辑本身和题目的“重力 + 任意排行”不一样，会算出错的答案

你说自己是“小学生”，那我尽量用生活比喻讲清楚，每一块都说得细一点。

一、最明显的硬伤：数组只开了 2000，但题目要 200000

你现在的代码：

pair<int, int> sss[int(2e3) + 3];
int thelowest[int(2e3) + 3];
int temp2 = 0, aq[int(2e3 + 3)], bq[int(2e3 + 38)];

这些 all 是 2000 多长 的数组。

但题目数据范围是：

每个数组长度 (k_i \le 2 \cdot 10^5)
所有数组长度总和 (\le 2 \cdot 10^5)

也就是说，某一个数组完全可以长成：[.... 200000 个数字 ....]

你却只开了 2000 个位置，就好像：

老师要你准备 200000 个小盒子装糖果，你只拿了 2000 个。
超过 2000 的糖果往后放，全都掉地上（内存越界）。

在 C++ 里，“数组越界”是未定义行为：
可能崩溃、可能跑出一堆奇怪数字、也可能在本机样例“看起来”没问题，但评测机一跑就寄。

👉 这个是致命错误 1：
所有固定长度的数组，要按题目上限开到 2e5 + 5 级别，或者干脆改用 vector。

二、你现在的逻辑在“模拟重力”这件事上就已经错了

先不管数组大小，就用很小的数据，看看你代码真正干了什么，再对比一下题目要求的“重力 + 排列行”的规则。

1. 你代码大概在干什么（用一张“水果排队”的比喻）

有好多行数组，先根据 长度从小到大 排序：

sort(sss + 1, sss + m + 1, cmp); // cmp 只按长度比较

先拿出最短的那一行，当作当前的 thelowest：

for (int j = 0; j < a[sss[1].second].size(); j++) {
    thelowest[j] = a[sss[1].second][j];
}
intervals.push_back({0, len-1});

想象成：现在“底行”是这一行。

然后按照长度从小到大的顺序，依次拿出下一行（越来越长的行）：
- 对每一个已经记录的区间 intervals[j] = [L, R]：
  - 把这行在 [L, R] 范围内的数字，和 thelowest[L..R] 比较：
```
if (thelowest[f] > a[cur][f]) suu = 1;
if (thelowest[f] < a[cur][f]) suu = 2;
```
  - 如果新数组在这一段更小（出现了 thelowest[f] > a[cur][f]）：
    - 就把这个区间后面的 interval 都删掉；
    - 再用新数组从 L 开始覆盖一整段：
```
intervals.push_back({tempp.first, a[cur].size()-1});
for (int z = tempp.first; z < a[cur].size(); z++) {
    thelowest[z] = a[cur][z - tempp.first];
}
```
- 最后再把这新数组余下的尾巴接在底行后面。

你大概想做的是：

“维护一条当前的底行，如果来了一个新行，它在某一段上更小，就用它替换掉那一整段。”

问题是：题目的“重力 + 任意排列行”的真实物理过程，根本不是这样的。

2. 真正的重力模型是怎样的？

假设有几行盒子（左对齐），你可以随便调换行的上下顺序。
然后放开手，重力往下：

每一列上，盒子会往下掉，变成“中间没有空”的一条竖直链；
每一列的“最底下”那个盒子，来自那一列最下面那一行中有盒子的那一行。

也就是说：
一旦你决定了行的排列顺序，所有列都会用同一套顺序来决定谁掉到最底。

不能出现“第 1 列让 A 行在最底，第 2 列让 B 行在最底，但 A/B 在两列中上下关系不一致”的情况。

而你现在的做法是：

“某一段我觉得新数组更小了，我就把这一段用新数组覆盖。”
这会导致同一个数组的某些位置被采纳，某些位置不被采纳，好像在不同列上，这个数组漂到了不一样的高度。

这在真实的重力+排列里是不可能发生的。

三、具体逻辑错误：对不齐位置，复制错位置

看这段关键代码：（我加点注释）

// 比较阶段：用 a[sss[i].second][f] 跟 thelowest[f] 比
for (int f = intervals[j].first; f <= intervals[j].second; f++) {
    if (thelowest[f] > a[sss[i].second][f]) suu = 1;
    if (thelowest[f] < a[sss[i].second][f]) suu = 2;
    if (suu == 1 or suu == 2) break;
}

// 如果新数组更小，就替换
if (suu == 1) {
    ...
    temppp = intervals.back();       // temppp.first = 某个 L
    ...
    intervals.push_back({temppp.first, a[cur].size() - 1});

    for (int z = temppp.first; z < a[cur].size(); z++) {
        thelowest[z] = a[cur][z - temppp.first];
    }
}

你在比较的时候，是对齐的：

f 从 L 到 R；
比较 thelowest[f] 和 a[cur][f]。

但是在拷贝的时候，你写的是：

thelowest[z] = a[cur][z - L]。

举个具体小例子就容易看出来错了：

例子：3 个数组

a1 = [1]       // 长度 1
a2 = [1, 2]    // 长度 2
a3 = [2, 1]    // 长度 2

过程简化一下：

排序后按长度：a1（1）, a2（2）, a3（2）
先用 a1 初始化：
- thelowest = [1, ?]
- intervals = [ [0,0] ]
处理 a2 = [1,2]：
- 在区间 [0,0] 比较：
  - thelowest[0] = 1, a2[0] = 1 → 相等，不更新
- 这一步后，你扩展尾巴，把 2 填到位置 1：
  - thelowest = [1, 2]
  - intervals = [ [0,0], [1,1] ]
处理 a3 = [2,1]：
- 先看区间 [0,0]：
  - thelowest[0] = 1, a3[0] = 2 → 新的更大（suu = 2），不替换
- 再看区间 [1,1]：
  - thelowest[1] = 2, a3[1] = 1 → 新的更小（suu = 1），准备替换
- temppp.first = 1、a3.size() = 2
- 复制阶段：
```
for (z = 1; z < 2; z++) {
    thelowest[1] = a3[1 - 1] = a3[0] = 2;
}
```
- 你把 thelowest[1] 改成了 a3[0] = 2，而我们判断更小用的是 a3[1] = 1！

也就是说：

你判断“新数组更好”用的是位置 f=1，拿的是 a3[1] = 1；
但你真正写入的时候，用的却是 a3[0] = 2；

结果：明明是因为 1 更小想替换，最后却填了个 2 进去，逻辑完全对不上。

👉 这是致命错误 2：比较和复制使用的下标对不齐，覆盖到了错误的位置。

四、还有一些“小坑”和“坏味道”

这些不是最核心的问题，但也会影响你 AC / 写好程序：

1. 固定长度数组 + 非标准语法

pair<int, int> sss[int(2e3) + 3];

这里用的是“变量作为数组长度”（VLA），在 C99 里是标准的，但在 C++ 标准里是不支持的，只是很多编译器（比如 g++）当成扩展给你用。

在一些更严格的编译器 / OJ 上，会直接编译不过。

更安全的写法是：

const int MAXN = 200000 + 5;
pair<int,int> sss[MAXN];
int thelowest[MAXN];

或者用 vector：

vector<pair<int,int>> sss(m + 1);
vector<int> thelowest(maxLen + 1);

2. 很多变量已经没用了

比如：

int temp2 = 0, aq[int(2e3 + 3)], bq[int(2e3 + 38)], cnt = 0, cnt1 = 0, wwwcnt = 0, wwwcnt1 = 0;

你已经不再用这几个数组和计数器了，但还留着：

看起来会让人误以为还有某种复杂逻辑；
自己以后回头看也更容易糊涂。

写代码时，删掉无用变量是个好习惯。

五、用一句话总结你现在这份代码的问题

从实现角度：

数组大小严重不够（只开到 2000），对题目数据范围（20 万）来说必崩；
用了 C++ 里非标准的 VLA 语法，可能在某些环境下编译不过；
在“用新数组覆盖底行”的时候，下标不对齐，导致比较用的位置和真正写入的位置不一样。

从算法设计角度：

你维护的“intervals + thelowest”的过程，不能正确模拟“把行重新排一下再统一受重力”的真实模型；
你可以构造出一个“底行”，但这个底行不一定真的能由某种行的排列 + 重力得到；
因此，即使不越界、不乱写，也会在某些测试用例上给出错误答案。

如果你愿意，我可以：

先帮你改成一个简洁很多、逻辑正确的版本（就是我前面给过的那份），
然后再用“小学生版”的讲法，一步一步画图，告诉你为什么那份代码是真正按照“重力 + 排列行”来算的。

有帮助，赞一个

去预览

0/2000

这里空空如也