自动搬运

查看原文

来自洛谷，原作者为

	chenly8128 God helps those who help themselves.

搬运于2025-08-24 23:09:03，当前版本为作者最后更新于2025-01-30 16:22:06，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

最难的是看懂题目。

本质上就是给出 $n$ 条线段，并给出第 $i$ 条线段上的 $a_i$ 个关键点，允许删除总计最多 $m-1$ 条不含关键点的子线段，问剩下的线段含有的点（不仅包括关键点）的总数是多少。

理解到这一步，直接使用整体减空白思想和贪心大法。

1. 首先，计算不删除任何子线段情况下，点的总数。
2. 接着，计算把每条线段中任意的相邻的两个关键点之间子线段删去，能够减少的点的个数。并存入一个数组 $a$。
3. 然后，$a$ 从大到小排序。
4. 最后，从总点数中减掉 $a$ 中大于 $0$ 的至多前 $m-1$ 项。

然后就好了，复杂度 $O(an\log_2{an})$，瓶颈在于排序。

CODE

// Author: chenly8128
// Created: 2025-01-30 15:58:36

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read(void) {
	int res = 0;bool flag = true;char c = getchar();
	while (c < '0' || c > '9') {flag ^= (c == '-');c = getchar();}
	while (c >= '0' && c <= '9') {res = (res << 3) + (res << 1) + (c ^ 48);c = getchar();}
	return flag ? res : -res;
}
vector <int> res;
vector <int> v;
int n,m,a;
ll sum = 0;
int main (void) {
	n = read();m = read();
	for (int i = 1;i <= n;i++) {
		a = read();
		v.clear();
		for (int i = 1;i <= a;i++) v.push_back(read());
		sort (v.begin(),v.end());
		for (int i = 1;i < a;i++)
			res.push_back(v[i]-v[i-1]-1);
		sum += v[a-1]-v[0]+1;
	}
	sort (res.begin(),res.end(),greater<int>());
	for (int i = 0;i < res.size();i++) {
		if (i >= m-1 || res[i] <= 0) break;
		sum -= res[i];
	}
	printf ("%lld\n",sum);
	return 0;
}