劲舞团K连击最长长度计算：基于时间戳的连续正确操作滑动窗口分析

我们来分析这个问题，并给出清晰的解题思路和代码实现。 --- ### 🎯 **问题理解** - 游戏记录文件 `log.txt` 中每行有三个字段： - 正确字符（期望按键） - 小蓝实际输入的字符 - 时间戳（毫秒） - **K 连击定义**：连续 K 次**正确敲击**（即 `正确字符 == 实际字符`），且**任意相邻两次敲击的时间间隔 ≤ 1000 ms**（即 ≤ 1 秒）。 - 目标：找出**最长的满足条件的连续正确敲击序列长度 K**，输出这个最大 K 值。 ⚠️ 注意： - 必须是**连续的记录索引**（即 log 文件中按时间顺序排列的行），但题目说“打出字符的时间对应的毫秒时间戳”，所以**必须先按时间戳排序**！ 👉 虽然通常日志是按时间顺序写的，但题目未明确保证，**为严谨起见，应先按时间戳升序排序**。 - “连续的 K 次正确敲击”指的是在**排序后的时间序列中，下标连续的 K 行**，每行都满足 `correct == actual`，且对所有 `i` 从 `start` 到 `start+K-2`，都有 `timestamp[i+1] - timestamp[i] <= 1000`。 --- ### ✅ **解题步骤** 1. **读取 log.txt**，解析每行：`correct`, `actual`, `timestamp`（转为 int）。 2. **按时间戳升序排序**（关键！避免因输入顺序混乱导致错误）。 3. **遍历排序后的记录，筛选出所有正确敲击的位置（即 `correct == actual`）**，并记录其时间戳。 - 得到一个「正确敲击事件」列表 `valid = [(ts0), (ts1), (ts2), ...]`，已按时间升序（因原数组已排序）。 4. **在线性扫描 valid 列表，找最长连续子序列，使得每相邻两个时间差 ≤ 1000 ms**： - 类似「滑动窗口」或「双指针」：维护当前连击起点 `left`，遍历 `right`，若 `ts[right] - ts[right-1] > 1000`，则断连 → 重置 `left = right`； - 否则继续延伸，更新最大长度 `max_k = max(max_k, right - left + 1)`。 > 💡 注意：连击要求**任意连续两次间隔 ≤ 1000ms**，即只要有一处间隔超时，整个连续段就断开。因此不能只看首尾，而要看**每一对相邻**。 --- ### 🧾 示例说明（辅助理解） 假设 valid 时间戳为： `[100, 1200, 2100, 3050, 4000]` 计算相邻差： `1200-100 = 1100 > 1000 ❌ → 断开` → 所以 `[100]` 长度 1 `[1200]` → `[1200,2100]`: 900 ✅ → `[1200,2100,3050]`: 3050-2100=950 ✅ → `[1200,2100,3050,4000]`: 4000-3050=950 ✅ → 这个子段长度为 4，是当前最长。 ✅ 所以答案是 `4`。 --- ### 🐍 Python 实现（可直接运行） ```python def main(): valid_timestamps = [] with open("log.txt", "r", encoding="utf-8") as f: for line in f: line = line.strip() if not line: continue parts = line.split() if len(parts) < 3: continue correct, actual, ts_str = parts[0], parts[1], parts[2] try: ts = int(ts_str) if correct == actual: valid_timestamps.append(ts) except ValueError: continue # 按时间戳排序（虽然 valid 是从排序后原数组提取的，但保险起见再排一次） valid_timestamps.sort() if not valid_timestamps: print(0) return max_k = 1 left = 0 for right in range(1, len(valid_timestamps)): # 检查上一对是否超时 if valid_timestamps[right] - valid_timestamps[right - 1] > 1000: left = right # 断开，新连击从 right 开始 else: # 否则延续连击 current_k = right - left + 1 if current_k > max_k: max_k = current_k print(max_k) if __name__ == "__main__": main() ``` --- ### ⚙️ 使用说明 - 确保当前目录下有 `log.txt`； - 每行格式示例（空格/制表符分隔均可，上面代码用 `split()`）： ``` A A 100 D D 1200 S F 2000 # 错误，跳过 D D 2100 D D 3050 D D 4000 ``` --- ### 🔍 进阶考虑（面试加分项） - 若时间戳精度高但存在重复（同一毫秒多次敲击）：`≤ 1000` 仍成立，无需特殊处理； - 若需输出具体哪一段（起止时间、位置），可扩展记录索引； - 大文件？可用生成器逐行处理 + 排序优化（如外部排序），但 N 一般不大； - 安全鲁棒性：跳过解析失败行，忽略空行，编码兼容 UTF-8。 --- ######[AI写代码神器 | 1439点数解答 | 2026-03-06 12:20:14]