「ROI 2025 Day2 T1」高质量休息 题解

题目分析

给定一个长度为 $n$ 的字符串，表示 $n$ 天的日程安排，其中：

• 0 表示工作日
• 1 表示休息日

我们可以将 $k$ 个工作日变为休息日，目标是最大化充实休假日的数量（连续休息天数 ≥ 2 的段中的所有天数）。

关键观察

1. 已有充实休假日：原字符串中已经存在的连续长度 ≥ 2 的休息段直接贡献充实休假日
2. 扩展机会：通过将特定的工作日变为休息日，可以连接孤立的休息日形成更长的连续段
3. 效率差异：不同的模式使用 1 个调休日获得的充实休假日数量不同

算法思路

模式分类与贪心策略

我们识别三种主要的扩展模式，按效率从高到低使用调休日：

1. 模式1：连接两个孤立的休息日（效率：3天/调休日）

模式："101"

• 原情况：1天休息 + 1天工作 + 1天休息
• 用 1 个调休日将中间的工作日变为休息日
• 结果：获得 3 天连续休息（全部成为充实休假日）
• 净增：3 个充实休假日

2. 模式2：扩展单个休息日（效率：2天/调休日）

模式："1"（孤立的休息日）

• 原情况：1天休息
• 用 1 个调休日将相邻的工作日变为休息日
• 结果：获得 2 天连续休息
• 净增：2 个充实休假日

3. 模式3：创建新的连续段（效率：1天/调休日）

• 用 2 个调休日创建新的 2 天连续休息段
• 或者用剩余的调休日扩展已有段

算法步骤

预处理阶段

1. 统计已有充实休假日：

   if(s[i]=='1'&&(s[i-1]=='0'||i==1)&&s[i+1]=='1'&&(i+1<=n)){
       t+=2; i+=2;
       for(;s[i]=='1'&&i<=n;++i,++t);
   }
   

   遍历字符串，找到所有连续长度 ≥ 2 的休息段，累加其天数到 t

2. 识别可扩展模式：

   • s1：统计 "101" 模式的数量
   • s2：统计孤立 "1" 的数量

查询处理

对于每个查询 $k$（可用调休日数量）：

int ans = t;  // 基础值：已有充实休假日
ans += min(s1, k) * 3;  // 优先使用模式1
k -= min(s1, k);
ans += min(s2, k) * 2;  // 再使用模式2
k -= min(s2, k);
ans += k;  // 最后使用剩余调休日

算法正确性

这种贪心策略的正确性基于：

1. 效率优先：模式1的单位调休日收益最高（3天），应优先使用
2. 无后效性：不同模式之间相对独立，使用一个模式不会影响其他模式的可用性
3. 完整性：考虑了所有可能的扩展方式

复杂度分析

• 预处理：$O(n)$，单次遍历字符串
• 查询处理：$O(1)$ 每个查询
• 总复杂度：$O(n + q)$，可以高效处理最大数据范围

样例验证

样例1

输入："000"（全工作日）

• 已有充实休假日：0
• 模式1：0，模式2：0
• $k=0$: 0
• $k=1$: 0（需要2个调休日才能创建连续段）
• $k=2$: 2（创建1个2天连续段）
• $k=3$: 3（创建1个3天连续段）

样例2

输入："1010"

• 已有充实休假日：0（没有连续≥2的段）
• 模式1：1（第1-3天形成"101"）
• 模式2：1（第4天是孤立的"1"）
• $k=0$: 0
• $k=1$: 3（使用模式1）
• $k=2$: 4（模式1 + 模式2）

总结

本题通过巧妙的模式识别和贪心策略，将复杂的调度问题转化为简单的分类计数问题。算法在线性时间内完成预处理，每个查询可在常数时间内回答，能够高效处理大规模数据。

算法标签：贪心算法 模式识别 分类讨论 预处理优化