P12302 [ICPC 2023 WF] 时差 题解
zjpwdyf
·
·
题解
0. 前言
有趣的贪心好题，卡了我三天。
教练和同学都是用 DP 写的，而贪心思路更简洁一些，于是来记录一下。
1. 题意
题面中关于睡眠时间表，表达得不是很清晰，这里来明确一下。
-
阶段一（0 \sim k 分钟）：睡觉。
-
阶段二（k \sim 2k 分钟）：清醒，此时不能睡觉，可以参加活动。
-
阶段三（2k \sim 3k 分钟）：可以睡觉或清醒。
-
阶段四（3k 分钟后）：若阶段三始终处于清醒状态，则需立即睡觉。
如下是两个不合法的的睡眠时间表，因为第二次睡眠开始时间或早或迟：
2. 思路
有一个天真的贪心思路：
一直睡觉，直到下一个活动的开始；然后一直不睡觉，直到第三个 k 分钟结束。
::::info[此思路模拟样例 1]{open}
$30 \sim \color{red}90$ 分钟：持续清醒，参加活动一、二
$90 \sim \color{purple}120$ 分钟：一直睡觉
$120 \sim \color{red}180$ 分钟：持续清醒，参加活动三
::::
然而这是错的。
```
3
10 21
25 29
30 33
```
上面这组样例，此思路会给出 `impossible`，然而它是有解的：
此贪心的错误在于：一直不睡觉，可能会错过宝贵的休息时间，从而对后续产生影响。
这是从固定睡眠的角度，考虑参加尽可能多的活动。
---
那能不能从活动的角度，考虑消耗尽可能短的睡眠呢？
这就引出了正确贪心思路：
> 倒序考虑每个活动，看这个活动前有无充足空闲时间，若有，则用来睡觉；若没有，则继续考虑上一个空闲时间……若一直找不到，则无解。
::::info[此思路模拟 hack 样例]{open}
考虑第三个活动：
时长 $33 - 30 = 3$ 分钟，活动前空闲 $30 - 29 = 1$ 分钟，时间不充足。
考虑第二、三个活动：
时长 $33 - 25 = 8$ 分钟，活动前空闲 $25 - 21 = 4$ 分钟，时间充足，将其用来睡觉。
考虑第一个活动：
时长 $21 - 10 = 11$ 分钟，活动前空闲 $11 - 0 = 10$ 分钟，时间充足，将其用来睡觉。
::::
容易注意到，睡觉只会对后续活动产生影响，而没有“前效性”，所以我们倒序枚举活动是恰当的。
---
最后一个细节：
已知空闲是充足的，那么怎么确定在空闲内，什么时候睡觉呢？
将空闲时间记为第 $x \sim y$ 分钟，需要保持清醒的时间记为第 $y \sim z$ 分钟，睡眠时长为 $l$。
有可能空闲之前就参加了很多活动，需立即入睡。故睡眠开始时间越早越好，即 $x$ 分钟时入睡。
全都用来睡觉是不理智的，这可能会导致后续清醒时间太长，影响后面的睡眠。
所以在保证睡眠充足的条件下，结束时间应越早越好。
由题意，最长清醒时长为睡眠时长的 $2$ 倍，所以清醒时间为 $x + l \sim x + 3l$ 分钟。应有 $z \le x + 3l$，解得 $l \ge \lceil \frac {z - x} 3\rceil$。
综上，睡觉时间为**第 $\color{black} x \sim x + \lceil \frac {z - x} 3 \rceil$ 分钟**。
## 3. 代码
有了上述思路，代码就极其简短了。
```cpp
#define ll long long
const int N = 2e5 + 5;
ll n, l[N], r[N];
vector <pair <ll, ll>> v; //pair 存储睡眠开始和结束时间
int main() {
ios :: sync_with_stdio(0);
cin.tie(0);
cin >> n;
for(int i = 1; i <= n; i++) cin >> l[i] >> r[i];
int i = n; //倒序枚举
while(i) {
int j = i;
while(j && (l[j] - r[j - 1]) * 2 < r[i] - l[j]) j--; //空闲太短
if(j == 0) { //找不到则无解
cout << "impossible";
return 0;
}
//此时 x = r[j - 1], y = l[j], z = r[i]
ll len = (r[i] - r[j - 1] + 2) / 3; //即除以 3 上取整
v.push_back({r[j - 1], r[j - 1] + len});
i = j - 1; //活动 i ~ j 被解决，应继续向前
}
int p = v.size();
cout << p << endl;
for(int i = p - 1; i >= 0; i--)
cout << v[i].first << ' ' << v[i].second << endl;
return 0;
}
```
## 4. 后记
很妙的贪心题，核心是“在完成当前任务的前提下，尽量避免影响后续”。
好久没写题解了，难免会有错误之处。如果有任何疑问，可以在评论区或私信指出。
如果这篇题解对您有帮助，记得点个赞哦。