CWOI S C0314 C 色

题意

U2FsdGVkX1+8uiG+PpDgKVLkStC7xLTSgybYosNzawTaA6uCLLvVEEuPxRrxWlT6
OqVxsKco36vWm0b7q6zTMswe8U/k4EKQ1JrjX8srH5AUH2JLR2lte2t8oT6ygpVX
iOefX4EweVO4+1FSuALHNNiTIV5LNSeISXfyA0B4HdDTm3/g9IVcx7FhwjjvcNEh
RdqojfMfNcYTLHsDFTLQlkI75hlDXSuR+0uuq6TDvw+BTWrlRAVqkBijrOU4X9Ja
bBtRpQqPK5Q8lorSfZTDaPoL2kn5FNoN1+aZaeGXnp4=

解析

分成两种情况，分出来的集合存在某个集合交为空，和不存在任何一个集合交为空。

若分出来的集合存在某个交为空，那么空集一定最多有一个，因为多个空集可以合并成一个空集。可以得到最优的方案一定是长度前 k-1 大的分别单独分一个集合，然后其他线段分成一个集合。

然后不存在某个集合交为空。

假设存在线段 [l1, r1] 和 [l2, r2]，使得 l1 <= l2 <= r2 <= l2，考虑 [l1, r1] 放在哪个集合。如果 [l1, r1] 不和 [l2, r2] 在一个集合，且不单独占一个集合，那么可以把 [l1, r1] 放到 [l2, r2] 同一个集合，这样答案不会更劣，而这时 [l1, r1] 实际上没有起什么影响，可以忽略。所以如果存在某个线段包含其他线段，我们可以直接忽略这个包含其他线段的线段，最后再枚举有多少个这种包含线段独占集合。

除去所有包含线段后，可以排序使得所有其他线段 l 和 r 都单调递增。可以证明，最优解一定可以调整成只有每个集合都的线段都是连续的。

A: |----------|
B:   |-------------|
C:     |----------------|
D:         |---------------|
E:          |---------------|

假设当前最优解中，ABDE 在一个集合，C 和 A 前面的某个线段在一个集合，那么你调整成 CDE 一个集合，AB 和前面的一个集合一定不劣。

令第 i 集合最靠前的线段为 $s_{i}$，那么长度可以写成：

$$r_{s_{0}} - l_{s_{1} - 1} + r_{s_{1}} - l_{s_{2} - 1} + r_{s_{2}} - l_{s{3} - 1} + \cdots + r_{s_{k-1}} - l_{n}$$

可以把每个位置 i 的 $r_{i} - l_{i-1}$ 排序，然后贪心取出前 k 大，再和前面包含线段组合一下即可。

时间复杂度 $O(n\log n)$。

实现

struct seg_t
{
	int l, r;
	seg_t() = default;
	seg_t(int l, int r) : l(l), r(r) {}
	int len() const { return r - l; }
};

long long solve1(int k, std::vector<seg_t> segs)
{
	int n = segs.size();
	std::sort(segs.begin(), segs.end(), [](const seg_t &a, const seg_t &b)
		  {
			  return a.len() > b.len();
		  });
	long long ans = 0;
	for (int i = 0; i < k - 1; i++) {
		ans += segs[i].len();
	}
	return ans;
}

std::pair<std::vector<seg_t>, std::vector<seg_t>> filter_contain(std::vector<seg_t> segs)
{
	std::vector<seg_t> good_seg, bad_seg;
	std::sort(segs.begin(), segs.end(), [](const seg_t &a, const seg_t &b)
		  {
			  if (a.r != b.r) {
				  return a.r < b.r;
			  } else {
				  return a.l > b.l;
			  }
		  });
	int last_l = -1;
	for (auto s : segs) {
		if (s.l <= last_l) {
			bad_seg.emplace_back(s);
		} else {
			good_seg.emplace_back(s);
			last_l = s.l;
		}
	}
	return {good_seg, bad_seg};
}

long long solve2(size_t k, std::vector<seg_t> segs)
{
	auto [good_seg, bad_seg] = filter_contain(std::move(segs));
	std::sort(bad_seg.begin(), bad_seg.end(), [](const seg_t &a, const seg_t &b)
		  {
			  return a.len() > b.len();
		  });

	std::vector<long long> w;
	for (size_t i = 1; i < good_seg.size(); i++) {
		w.emplace_back(-good_seg[i - 1].l + good_seg[i].r);
	}
	std::sort(w.begin(), w.end(), std::greater<>());
	std::vector<long long> f(k + 1), g(k + 1);
	for (size_t i = 0; i < k; i++) {
		if (i < w.size()) {
			f[i + 1] = f[i] + w[i];
		}
		if (i < bad_seg.size()) {
			g[i + 1] = g[i] + bad_seg[i].len();
		}
	}

	auto ans = std::numeric_limits<long long>::min();
	for (int i = 1; i <= k; i++) {
		ans = std::max(ans, f[i - 1] + good_seg[0].r - good_seg.back().l + g[k - i]);
	}
	return ans;
}