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,得到最佳答案。