欢迎光临散文网 会员登陆 & 注册

CF竞赛题目讲解_CF121D(双指针顺序扫描)

2022-09-23 10:52 作者:Clayton_Zhou  | 我要投稿

https://codeforces.com/contest/121/problem/D


题意:

给出n个区间,区间可以左右移动,所有区间移动幅度总和最多为K。

问最多有多少个lucky number同时在n个区间中。


题解:

双指针顺序扫描,

two pointers处理lucky number的某个区间。

check:

第一个条件是区间长度不能小于所有区间中最短的;

第二个条件是所有区间移动到指定区间的代价小于K。


左右端点分开处理,如果目标为lucky[i],

那么所有左端点 > lucky[i]的都必须向左移动过来。

那么所有右端点 < lucky[i]的都必须向右移动过来。


向右移动two pointers,得到最佳答案。


CF竞赛题目讲解_CF121D(双指针顺序扫描)的评论 (共 条)

分享到微博请遵守国家法律