题解：P7562 [JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)

· · 题解

[JOISC 2021 Day4] イベント巡り 2 (Event Hopping 2)

题目背景

本题是 第20回日本情報オリンピック 2020/2021春季トレーニング合宿 的题目，原题链接为 JOISC 2021 Day4 T1。此题要求在一个活动序列中选择 k 个不重叠的活动，并输出字典序最小的选择方案。

题目描述

IOI Park 将有 n 场活动，编号从 1 到 n。活动 i 从时间 L_i+10^{-1} 到时间 R_i-10^{-1} 举行。数据保证 L_i 和 R_i 是整数。JOI 君决定参加其中的 k 个活动，但不能在活动中间加入或离开。判断 JOI 君是否可以参加 k 个活动，如果可以，输出所有的 k 个活动的编号。

输入格式

输入包含两行，第一行是两个正整数 n, k，第二行起每行包含两个正整数 L_i, R_i。

输出格式

如果可以参加 k 个活动，输出 k 个活动的编号，否则输出 -1。

解题思路

主要思路

  1. 贪心选择：由于题目要求输出字典序最小的选择方案，我们可以从活动 1 到 n 依次尝试选择。
  2. 区间表示：将每个活动表示为一个区间 [L_i, R_i]。
  3. 区间查询：使用数据结构（如 set）来维护当前可用的空闲区间，并快速查询某个区间是否可用。
  4. 倍增优化：使用倍增和预处理的方法来快速查询某个区间内最多可以选择的活动数量。

    算法细节

  5. 区间表示：将所有活动的左右端点加入到 vector 中，并进行去重和排序，得到一个离散化后的区间。
  6. 预处理：利用倍增思想预处理 dp 数组，其中 dp[i][j] 表示从位置 i 开始，最多可以选择 2^j 个活动的最远位置。
  7. 区间查询：利用预处理得到的 dp 数组，可以快速查询某个区间内最多可以选择的活动数量。
  8. 贪心选择：遍历每个活动，如果该活动可以加入当前选择方案，则更新当前可用的空闲区间，并将该活动加入选择方案。

    代码实现

    #include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
struct Segment {
int left, right;
// ...
};
// ...
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> numSegments >> maxK;
// ...
preprocess();
segmentSet.insert(createSegment(0, allPositions.size() - 1));
vector<int> selectedSegments;
set<Segment>::iterator it;
int lastCount = rangeQuery(0, allPositions.size() - 1);
for (int i = 1; i <= numSegments && selectedSegments.size() < maxK; i++) {
    // ...
}
if (selectedSegments.size() == maxK) {
    // ...
} else {
    cout << -1;
}
return 0;
}

    复杂度分析

    • 时间复杂度：O(n \log n)。主要是预处理 dp 数组和查询的时间。
    • 空间复杂度：O(n \log n)。主要是 dp 数组和 set 的大小。

      总结

      本题是一个结合贪心、数据结构（set）、倍增优化的综合题目。通过有效的预处理和查询，可以在合理的时间复杂度内解决题目要求。