专栏文章

P12302 [ICPC 2023 WF] 时差 题解

zzjpwdyf
P12302题解参与者 6已保存评论 5

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
5 条
当前快照
1 份
快照标识符
@mio7x4wd
此快照首次捕获于
2025/12/02 14:49
3 个月前
此快照最后确认于
2025/12/02 14:49
3 个月前
查看原文

0. 前言

有趣的贪心好题，卡了我三天。
教练和同学都是用 DP 写的，而贪心思路更简洁一些，于是来记录一下。

1. 题意

题面中关于睡眠时间表，表达得不是很清晰，这里来明确一下。
  • 阶段一（0∼k0 \sim k 分钟）：睡觉。
  • 阶段二（k∼2kk \sim 2k 分钟）：清醒，此时不能睡觉，可以参加活动。
  • 阶段三（2k∼3k2k \sim 3k 分钟）：可以睡觉或清醒。
  • 阶段四（3k3k 分钟后）：若阶段三始终处于清醒状态，则需立即睡觉。
如下是两个不合法的的睡眠时间表，因为第二次睡眠开始时间或早或迟：

2. 思路

有一个天真的贪心思路：
一直睡觉，直到下一个活动的开始；然后一直不睡觉，直到第三个 kk 分钟结束。
此思路模拟样例 1
0∼300 \sim \color{purple}30 分钟：一直睡觉
30∼9030 \sim \color{red}90 分钟：持续清醒，参加活动一、二
90∼12090 \sim \color{purple}120 分钟：一直睡觉
120∼180120 \sim \color{red}180 分钟：持续清醒，参加活动三
然而这是错的。
CPP
3
10 21
25 29
30 33
上面这组样例，此思路会给出 impossible，然而它是有解的：
此贪心的错误在于：一直不睡觉，可能会错过宝贵的休息时间，从而对后续产生影响。
这是从固定睡眠的角度，考虑参加尽可能多的活动。
那能不能从活动的角度，考虑消耗尽可能短的睡眠呢？
这就引出了正确贪心思路：
倒序考虑每个活动，看这个活动前有无充足空闲时间，若有，则用来睡觉；若没有，则继续考虑上一个空闲时间……若一直找不到，则无解。
此思路模拟 hack 样例
考虑第三个活动：
时长 33−30=333 - 30 = 3 分钟，活动前空闲 30−29=130 - 29 = 1 分钟，时间不充足。
考虑第二、三个活动：
时长 33−25=833 - 25 = 8 分钟，活动前空闲 25−21=425 - 21 = 4 分钟，时间充足，将其用来睡觉。
考虑第一个活动：
时长 21−10=1121 - 10 = 11 分钟，活动前空闲 11−0=1011 - 0 = 10 分钟，时间充足，将其用来睡觉。
容易注意到，睡觉只会对后续活动产生影响，而没有“前效性”，所以我们倒序枚举活动是恰当的。
最后一个细节：
已知空闲是充足的，那么怎么确定在空闲内，什么时候睡觉呢？
将空闲时间记为第 x∼yx \sim y 分钟，需要保持清醒的时间记为第 y∼zy \sim z 分钟，睡眠时长为 ll。
有可能空闲之前就参加了很多活动，需立即入睡。故睡眠开始时间越早越好，即 xx 分钟时入睡。
全都用来睡觉是不理智的，这可能会导致后续清醒时间太长，影响后面的睡眠。
所以在保证睡眠充足的条件下，结束时间应越早越好。
由题意，最长清醒时长为睡眠时长的 22 倍，所以清醒时间为 x+l∼x+3lx + l \sim x + 3l 分钟。应有 z≤x+3lz \le x + 3l，解得 l≥⌈z−x3⌉l \ge \lceil \frac {z - x} 3\rceil。
综上，睡觉时间为第 x∼x+⌈z−x3⌉\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. 后记

很妙的贪心题，核心是“在完成当前任务的前提下，尽量避免影响后续”。
好久没写题解了，难免会有错误之处。如果有任何疑问，可以在评论区或私信指出。
如果这篇题解对您有帮助，记得点个赞哦。

评论

共 5 条评论，欢迎与作者交流。

正在加载评论...