2023.11.15 信息学日志

1. CF1409E Two Platforms

题目描述

https://www.luogu.com.cn/problem/CF1409E

题目概况

来源：Codeforces

洛谷难度：$绿题$

CF难度：$1800$

标签：二分 后缀最值

思路点拨

前期操作：

• 显而易见纵坐标没什么用死
• 本能将横坐标排序

题眼剖析:

• 题目仅有 2 个板子，如果默认放好一个板子，另一个板子放在这个板子右侧的最优位置。

根据分析引入了 2 个概念：

1. 当板子以某个点为开头所能覆盖的点数
2. 在某一个点后放置板子的最优位置

顺着这条思路想处理方法：

• 定义 $f_{[i]}$ 表示板的左边顶着点 $i$ 的横坐标，所能覆盖的点的数量，这个可以用二分去做。（显然让板的端点顶着某题目所给点是优秀的策略）
• 这是定义 $m{x}_{[i]}$ 表示 $\max (f_{[j]})(i\le j\le n，j\in \mathbb{Z})$

稍微转一下就OK了

时间复杂度： $\mathrm{O}(n?lo{g}_2(n))$

AC。

2. CF1804D Accommodation

题目描述

https://www.luogu.com.cn/problem/CF82C

题目概况

来源：Codeforces

洛谷难度：$蓝题$

CF难度：$2000$

标签：贪心 枚举

思路点拨