题目链接：https://codeforces.com/problemset/problem/1821/D
题目大意
在一条数轴上有无穷个点，下标为 \(0, 1, 2, \ldots\)，初始时每个点都是白色的。
你控制着一个机器人，初始时机器人位于坐标为 \(0\) 的那个点。
机器人有两种状态：激活状态 和 非激活状态。
当处于激活状态时，机器人所在的点都会被染成黑色。
处于非激活状态时，机器人所在的点不会被染成黑色。
初始时机器人处于非激活状态。
你可以对这个机器人进行若干次操作，操作分为三种类型。每一次操作，你可以选择如下三种操作之一执行：
- 将机器人的位置像数轴的正方向移动一个单位（即：若当前机器人在坐标 \(x\)，则执行一次该操作后机器人将移动到坐标 \(x+1\) 的那个点）；
- 激活机器人：该操作只有当机器人处于非激活状态时才能执行，执行该操作后机器人将变为 激活状态；
- 撤销激活机器人：该操作只有当机器人处于激活状态时才能执行，执行该操作后机器人将变为 非激活状态。
有 \(n\) 个区间，第 \(i\) 个区间用 \([l_i, r_i]\) 表示。
你需要使用最少的操作次数，将至少 \(k\) 个点染成黑色，但是有一个限制，就是：这些染成黑色的点必须包含在至少一个给定的区间中，这也就是说，如果你要将坐标为 \(x\) 的那个点染成黑色，则必须保证存在一个 \(i(1 \le i \le n)\) 满足 \(l_i \le x \le r_i\)。
同时，本题也要求操作结束时机器人恢复到非激活状态（这也就意味着最少操作次数对应的最后一次操作是 撤销激活机器人）。
问：至少需要进行几次操作能够使至少 \(k\) 个点被染成黑色，且最终机器人处于非激活状态？
解题思路
首先是考虑从前往后枚举第 \(i\) 个线段。
考虑只对前 \(i\) 个线段里面的点进行染色。那么会出现两种情况：
- 情况1：前 \(i\) 个线段里面可以被染色的点的个数 \(\lt k\) 个 —— 此时因为点的数量不够，所以不做讨论；
- 情况2：前 \(i\) 个线段里面可以被染色的点的个数 \(\ge k\) 个，此时需要重点分析。
当前 \(i\) 个线段里面可以被染色的点的个数 \(\ge k\) 个时，我们还需要考虑 —— 最优解有没有给第 \(i\) 个线段中的点染色？
如果最优解没有给第 \(i\) 个线段中的点染色，则该情况可以直接转移到前 \(i-1\) 个线段的情况（因为我们时枚举前 \(i\) 个线段的，枚举前 \(i\) 个线段之前肯定已经枚举了前 \(i-1\) 个线段，所以这种情况实际上已经分析过了）。
所以此时的情况肯定是给第 \(i\) 个线段中的点染色的。
首先，对于前面的所有线段，只要是选择染色的，将前面这些线段中的点全部都染色肯定不会差，因为：
对于一个线段，只要有一个点选择染色了，那么肯定具有 激活（原题中的 shift）和 撤销激活（原题中的 release shift）操作了，此时再对这个线段中的其它点进行染色的额外操作此时是确定的，多染一个点只需要多操作一次。
所以，对于前 \(i-1\) 个线段：
- 要么选择全都不染（这个线段弃用掉）；
- 要么选择全都染（然后第 \(i\) 个线段把剩余的个数补齐）。
所以此时需要考虑的是前 \(i-1\) 个线段中哪些需要弃用掉。
我一开始有一种错误的贪心思想，就是在保证前 \(i\) 个线段中保留的线段对应的点的个数 \(\ge k\) 的情况下，尽量多删除前面的长度小的线段，但是发现这种错误思想是错误的。举个反例：
1
2 3
1 3
2 5
此时：当 \(i = 2\) 时，弃用掉第一段的最少操作次数为 \(7\)；不弃用第 \(1\) 段的操作此时是 \(6\)。
只有长度为 \(1\) 的线段才有可能被弃用。
为什么呢，因为在考虑前 \(i\) 个线段并且第 \(i\) 个线段是需要激活的情况下，是肯定需要移动到 \(l_i\) 的，而 \(r_{i-1} \lt l_i\)，对于一个长度 \(\ge 2\) 的线段（假设为第 \(j\) 个线段）\([l_j, r_j]\)，这些点段中的点都是要移动到的，当线段中的点数 \(\ge 2\) 时，只需要两步额外的操作（激活/shift 和 撤销激活release shift）就能够使这个线段中的所有点都染色（这不是很香嘛），至少不会比在第 \(i\) 个线段中向右移动一格要花更多的操作次数。
而对于长度为 \(1\) 的线段，移动也是需要移动的，所以不考虑移动的开销。但是如果给这一个点染色需要额外操作两次（激活/shift 和 撤销激活release shift）。而后面的第 \(i\) 个线段只需要多移动依次就能多一个点染色。所以对于长度为 \(1\) 的点，弃用它们更优。
所以，只有长度为 \(1\) 的线段才有可能被弃用。
但是弃用归弃用，对于每个枚举到的 \(i\)，当前 \(i\) 个线段的对应的所有可以染色的点的数量已经 \(\ge k\) 时，不能启用到剩余点的个数 \(\lt k\) —— \(\lt k\) 了就不是一个可发的答案了。
综上所述，就是枚举前 \(i\) 个线段，然后把前面长度为 \(1\) 的线段能弃用的都弃用了。那么此时，假设：
- 没有被弃用的线段对应的点的数量为 \(sum\)
- 没有被弃用的线段的数量是 \(cnt\) 个
则：考虑到从坐标 \(0\) 移动到 \(r_i\)，并且没有弃用的线段都染色了，那么：
- 移动带来的花费是 \(r_i\)，
- 每个线段激活和撤销激活的花费是 \(cnt \times 2\)
所以给前 \(i\) 个线段中没有弃用的线段中的点都染色的花费是 \(r_i + cnt \times 2\)。
但是，因为我只需要给 \(k\) 个点染色就可以了，但是我却选择给了 \(sum\) 个点染色（\(sum \ge k\)），那么在最后一个线段中，我其实可以减少 \(sum - k\) 个点的染色（减小 \(sum - k\) 次向右的移动），此时答案的一个候选项是：
\(r_i + cnt \times 2 - (sum - k)\)
而我的答案就是所有合法的 \(r_i + cnt \times 2 - (sum - k)\) 的最小值。
示例程序
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
int T, n, k, l[maxn], r[maxn];
int cal() {
int ans = -1, cnt = 0, sum = 0, cnt1 = 0;
for (int i = 1; i <= n; i++) {
sum += r[i] - l[i] + 1;
cnt++;
cnt1 += (l[i] == r[i]);
if (sum >= k) {
int x = min(sum-k, cnt1);
sum -= x;
cnt1 -= x;
cnt -= x;
int tmp = r[i] + cnt * 2 - (sum - k);
if (ans == -1 || ans > tmp)
ans = tmp;
}
}
return ans;
}
int main() {
scanf("%d", &T);
while (T--) {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++) scanf("%d", l+i);
for (int i = 1; i <= n; i++) scanf("%d", r+i);
printf("%d\n", cal());
}
return 0;
}