丝路互市排期：开放区间合并与峰值日统计 完整解题档案

档案概况

题目、题干与输入输出

正式题面

源文件：official-prompt.md

规则来源

• 赛项说明页码：12-13
• 训练题主题：丝路互市排期：开放区间合并与峰值日统计
• 所属赛道：丝路文化赛道

题目背景

丝路互市会在一年内开放多次。每场活动覆盖一个闭区间日期，筹备团队想知道最多同时开放几场、最早在哪一天达到峰值，以及所有至少有一场互市开放的连续日期区间。

任务描述

• 读取全部互市开放区间并统计每天的开放场次。
• 输出最大同时开放场次数和最早峰值日。
• 把所有活跃日期合并成不间断区间并输出。

输入格式

1. 第一行输入 n D，表示活动数量和总日历天数。
2. 接下来 n 行每行输入 l r，表示一场互市在第 l 天到第 r 天开放。

输出格式

1. 第一行输出 max_open=某天同时开放的最大场次数。
2. 第二行输出 first_peak_day=最早达到峰值的日期。
3. 第三行输出 merged= 后接合并后的连续活跃区间，格式如 1-5|7-9。

数据范围与说明

• 1 <= D <= 365。
• 1 <= n <= 500。
• 1 <= l <= r <= D。
• 相邻活跃日视为同一连续开放区间。
• 若多个日期同时达到峰值，输出最早日期。

样例输入

5 10
1 3
2 5
6 6
7 9
9 10

样例输出

max_open=2
first_peak_day=2
merged=1-10

样例解释

• 第 2 天和第 3 天都有两场互市同时开放，因此峰值为 2。
• 最早达到峰值的日期是第 2 天。
• 所有活跃日期连成 1-10，所以 merged=1-10。

知识点清单

• 差分数组做区间加一标记。
• 前缀和还原每天开放数。
• 最早峰值位置维护。
• 扫描正数区间并合并连续段。
• r + 1 边界处理。

约束拆解

源文件：parsed-constraints.md

显式约束

• 1 <= D <= 365。
• 1 <= n <= 500。
• 1 <= l <= r <= D。
• 相邻活跃日视为同一连续开放区间。
• 若多个日期同时达到峰值，输出最早日期。

建模拆解

• 先明确输入的实体和字段，再把它们翻译成 差分数组 + 连续区间合并 需要的数据结构。
• 把输出中每一项指标都和中间变量对应起来，避免最后临时拼装。
• 先用样例手推一次，再确认边界条件是否都能走到正确分支。

易错边界

• 开放区间覆盖到最后一天时，差分数组仍要安全处理。
• 多个相邻区间只要中间不断开，就应合并为一个大区间。
• 峰值可能在多个日期重复出现，只能取最早日期。

计分模型

源文件：scoring-model.md

判题方式

• 主判题方式：exact
• 主算法：差分数组 + 连续区间合并

判题重点

• 重点校验公式、排序规则和格式化输出是否完全一致。
• 隐藏数据会覆盖边界值、重复值和最小规模输入。

公开样例建议

• 至少准备 1 组题面样例、2 组边界样例和 2 组自定义回归样例。
• 多输出题必须验证所有字段都来自同一套方案。

隐藏数据建议

• 准备完全不相交、完全相连和部分重叠三类区间结构。
• 准备峰值出现在首日和末日的样例。
• 准备只有一场活动和多场单日活动的边界数据。

验收清单

源文件：acceptance-checklist.md

• 正式题面、约束拆解、评分说明均已补齐
• 样例输入输出已定义并通过主实现校验
• python 主实现已提供并与样例输出对齐
• cpp 主实现已提供并与样例输出对齐
• 调试记录、决策记录、验证计划已补齐
• 可由 20-tools/assemble_case_dossiers.py 汇总为完整解题档案

样例输入输出

样例输入：sample.in

5 10
1 3
2 5
6 6
7 9
9 10

样例输出：sample.out

max_open=2
first_peak_day=2
merged=1-10

题解、建模与最终解法

自动整理的解题流程

• 题目主题：丝路互市排期：开放区间合并与峰值日统计
• 题目摘要：利用差分数组还原每天的开放场次数，并合并连续活跃日区间。
• 判题提示：该题以精确输出为主，最终程序需要重点保证公式、顺序和格式完全一致。
• 先完成输入、对象、约束和输出的四步建模，再落到具体算法和实现。
• 优先用样例验证最小流程，再补边界测试和错误分支。

解题思路

源文件：solution-rationale.md

1. 问题重述

利用差分数组还原每天的开放场次数，并合并连续活跃日区间。

2. 数据结构与建模

• 主算法：差分数组 + 连续区间合并
• 输入拆解后对应的数据结构要和输出项一一对应。
• 需要重点维护的状态包括：题目实体、核心指标、中间结果和最终答案。

3. 算法步骤

1. 对每个开放区间执行一次差分标记。
2. 按天顺序恢复每天的开放场次数，并维护峰值与最早峰值日。
3. 在扫描过程中记录所有活跃日段的起止位置。
4. 把活跃区间按指定格式序列化输出。

4. 正确性说明

• 每一步都严格对应题面给出的规则或约束。
• 所有输出字段都来自同一份计算过程，不会出现“各算各的”的不一致情况。
• 边界情况通过单独分支或统一规则处理，保证程序在最小规模和重复值情况下也稳定。

5. 复杂度分析

• 复杂度取决于输入规模和主算法，但整体设计保持在初中组可讲解、可验证的范围内。
• 只保留必要状态，不引入超出题意的数据结构。

6. 易错点

• 开放区间覆盖到最后一天时，差分数组仍要安全处理。
• 多个相邻区间只要中间不断开，就应合并为一个大区间。
• 峰值可能在多个日期重复出现，只能取最早日期。

7. 知识点清单

• 差分数组做区间加一标记。
• 前缀和还原每天开放数。
• 最早峰值位置维护。
• 扫描正数区间并合并连续段。
• r + 1 边界处理。

设计决策记录

源文件：decision-log.md

• 选择 差分数组 + 连续区间合并 作为主算法，因为它能直接覆盖题目的核心约束。
• 开放场次和区间合并都建立在逐日活跃数之上，因此一次差分扫描即可解决。
• 日历天数上限较小，但仍应保持结构化实现，便于扩展输出。
• Python 与 C++ 版本统一输出格式，便于双语训练和证据采集。

验证计划

源文件：validation-plan.md

• 先验证题面公开样例，确保基础流程无误。
• 准备完全不相交、完全相连和部分重叠三类区间结构。
• 准备峰值出现在首日和末日的样例。
• 准备只有一场活动和多场单日活动的边界数据。
• 最后再补 1 组手工构造的极小数据，确认程序不会依赖特殊输入规模。

备选方案

源文件：alternatives.md

最终代码与实现

Python 主实现

源文件：main.py

• 实现状态：当前已有可执行实现

import sys


def solve(data: str) -> str:
    tokens = list(map(int, data.split()))
    if not tokens:
        return ""
    it = iter(tokens)
    n = next(it)
    days_total = next(it)
    diff = [0] * (days_total + 3)
    for _ in range(n):
        left = next(it)
        right = next(it)
        diff[left] += 1
        diff[right + 1] -= 1
    active = 0
    max_open = -1
    first_peak = 0
    merged = []
    start = None
    for day in range(1, days_total + 1):
        active += diff[day]
        if active > max_open:
            max_open = active
            first_peak = day
        if active > 0 and start is None:
            start = day
        if active == 0 and start is not None:
            merged.append((start, day - 1))
            start = None
    if start is not None:
        merged.append((start, days_total))
    merged_text = "|".join(f"{left}-{right}" for left, right in merged) if merged else "NONE"
    return "\n".join(
        [
            f"max_open={max_open}",
            f"first_peak_day={first_peak}",
            f"merged={merged_text}",
        ]
    )


if __name__ == "__main__":
    sys.stdout.write(solve(sys.stdin.read()).strip())
    sys.stdout.write("\n")

C++ 对照实现

源文件：main.cpp

• 实现状态：当前已有可执行实现

#include <iostream>
#include <string>
#include <utility>
#include <vector>

using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, days_total;
    if (!(cin >> n >> days_total)) {
        return 0;
    }
    vector<int> diff(days_total + 3, 0);
    for (int i = 0; i < n; ++i) {
        int left, right;
        cin >> left >> right;
        ++diff[left];
        --diff[right + 1];
    }
    int active = 0;
    int max_open = -1;
    int first_peak = 0;
    vector<pair<int, int>> merged;
    int start = -1;
    for (int day = 1; day <= days_total; ++day) {
        active += diff[day];
        if (active > max_open) {
            max_open = active;
            first_peak = day;
        }
        if (active > 0 && start == -1) {
            start = day;
        }
        if (active == 0 && start != -1) {
            merged.push_back({start, day - 1});
            start = -1;
        }
    }
    if (start != -1) {
        merged.push_back({start, days_total});
    }
    cout << "max_open=" << max_open << "\n";
    cout << "first_peak_day=" << first_peak << "\n";
    cout << "merged=";
    if (merged.empty()) {
        cout << "NONE";
    } else {
        for (size_t i = 0; i < merged.size(); ++i) {
            if (i) {
                cout << '|';
            }
            cout << merged[i].first << '-' << merged[i].second;
        }
    }
    cout << "\n";
    return 0;
}

代码执行与运行结果

最新成功运行

PY 运行输出摘录

max_open=2
first_peak_day=2
merged=1-10

CPP 运行输出摘录

max_open=2
first_peak_day=2
merged=1-10

全部运行记录索引

调试、修正与流程留痕

调试日志

源文件：debug-journal.md

失败案例目录

源文件：failure-catalog.md

编码过程记录

源文件：implementation-journal.md

全流程文件导航

• 题目总览：s3-jh-06-market-calendar/README.md
• 题面与约束：official-prompt.md、parsed-constraints.md、scoring-model.md、acceptance-checklist.md
• 代码与样例：10-cases/s3-jh-06-market-calendar/02-solution
• 运行证据：10-cases/s3-jh-06-market-calendar/03-execution
• 调试过程：debug-journal.md、failure-catalog.md、implementation-journal.md
• 解法说明：solution-rationale.md、decision-log.md、validation-plan.md、alternatives.md
• 交付档案：final-report.md、appendix-code.md、appendix-runs.md、evidence-pack.md