题解：P12505 「ROI 2025 Day2」充实的假期

· · 题解

问题分析

我们需要计算在给定的实习日程中，对于每个可能的调休天数 k，小明最多能获得多少个‌充实休假日‌（即连续两天或以上的休息日）。关键在于如何高效地处理多个查询，并找到最优的调休策略。

解题思路

‌预处理原始休息日段‌：首先，我们需要找到原始日程中所有的连续休息日段（即连续的 '1'），并记录它们的长度和位置。

‌处理工作日段‌：

对于工作日段（即连续的 '0'），我们需要考虑如何通过调休将它们转换为休息日，以增加充实休假日的数量。

‌滑动窗口优化‌：

对于每个查询 k，我们需要找到最优的工作日段，使得用 k 个调休日填充后，能最大化充实休假日的数量。这可以通过滑动窗口或双指针技术来高效计算。 代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

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

    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;

    // 预处理：记录所有连续的休息日段（'1'的连续块）
    vector<int> rest_segments;
    for (int i = 0; i < n; ) {
        if (s[i] == '1') {
            int j = i;
            while (j < n && s[j] == '1') j++;
            rest_segments.push_back(j - i); // 记录连续休息日的长度
            i = j;
        } else {
            i++;
        }
    }

    // 预处理：记录所有工作日段（'0'的连续块）
    vector<int> work_segments;
    for (int i = 0; i < n; ) {
        if (s[i] == '0') {
            int j = i;
            while (j < n && s[j] == '0') j++;
            work_segments.push_back(j - i); // 记录连续工作日的长度
            i = j;
        } else {
            i++;
        }
    }

    // 预处理：计算每个工作日段被填充后能增加的充实休假日数量
    vector<int> benefits;
    for (int len : work_segments) {
        // 填充一个工作日段可以增加 min(len, 2) 的充实休假日（最多2天）
        benefits.push_back(min(len, 2));
    }

    // 对 benefits 进行排序，以便贪心选择最优的工作日段
    sort(benefits.begin(), benefits.end(), greater<int>());

    // 预处理：计算前缀和，方便快速查询前 k 个最大 benefits 的和
    vector<int> prefix_sum(benefits.size() + 1, 0);
    for (int i = 0; i < benefits.size(); i++) {
        prefix_sum[i + 1] = prefix_sum[i] + benefits[i];
    }

    // 预处理：计算原始充实休假日数量
    int original = 0;
    for (int len : rest_segments) {
        if (len >= 2) original += len - 1; // 每个连续休息日段贡献 len-1 个充实休假日
    }

    // 处理每个查询
    while (q--) {
        int k;
        cin >> k;
        // 最多可以选择 min(k, benefits.size()) 个工作日段
        int max_benefit = prefix_sum[min(k, (int)benefits.size())];
        cout << original + max_benefit << '\n';
    }

    return 0;
}

代码解释

‌输入处理‌：

读取实习天数 n、查询数量 q 和日程字符串 s。 ‌预处理休息日段和工作日段‌：遍历字符串 s，记录所有连续的休息日段和工作日段的长度。

‌计算工作日段的收益‌：每个工作日段被填充后，最多能增加 2 个充实休假日（因为需要连续两天或以上）。 ‌贪心选择最优工作日段‌：对工作日段的收益进行降序排序，并计算前缀和，以便快速查询前 k 个最大收益的和。

‌计算原始充实休假日数量‌：遍历所有休息日段，计算原始日程中的充实休假日数量

‌处理查询‌：对于每个查询 k，输出原始充实休假日数量加上前 k 个最大工作日段收益的和。

复杂度分析

‌预处理阶段‌：O(n) 时间遍历字符串，O(m log m) 时间排序工作日段收益（m 是工作日段的数量）。 ‌查询阶段‌：每个查询 O(1) 时间（利用前缀和）。 ‌总复杂度‌：O(n + m log m + q)，适用于题目给定的约束条件。