CF1893C Freedom of Choice 题解

Freedom of Choice

传送门

题面翻译

让我们把多集合 { b 1 , b 2 , … , b l e n } \{b_1, b_2, \ldots, b_{len}\} {b1?,b2?,…,blen?} 的反美定义为多集合中数字 $len$ 出现的次数。

我们给出了 $m$ 个多集，其中 $i$ 个多集包含 $n_i$ 个不同的元素，具体来说就是：数字 $a_{i,1}$ 的 $c_{i,1}$ 个副本，数字 $a_{i,2},\dots ,c_{i,n_i}$ 的 $c_{i,2}$ 个副本，数字 $a_{i,n_i}$ 的 $a_{i,2},\dots ,c_{i,n_i}$ 个副本。可以保证 $a_{i,1}<a_{i,2}<\dots <a_{i,n_i}$ 。还给出了数字 $l_1,l_2,\dots ,l_m$ 和 $r_1,r_2,\dots ,r_m$ ，使得 $1\le l_i\le r_i\le c_{i,1}+\dots +c_{i,n_i}$ .

让我们创建一个最初为空的多集 $X$ 。然后，对于从 $1$ 到 $m$ 的每一个 $i$ ，你必须执行下面的操作次：

1. 选择某个 $v_i$ ，使得 $l_i\le v_i\le r_i$ 为空
2. 从 $i$ /th多集合中选择任意 $v_i$ 个数字，并将它们添加到多集合 $X$ 中。

你需要以这样的方式选择 $v_1,\dots ,v_m$ 和添加的数字，使得得到的多集 $X$ 具有最小可能的反美感。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $t$ ( $1\le t\le 10^4$ ) - 测试用例的个数。测试用例说明如下。

每个测试用例的第一行包含一个整数 $m$ ( $1\le m\le 10^5$ ) - 给定多集合的个数。

然后，从 $1$ 到 $m$ 的每个 $i$ 都包含一个由三行组成的数据块。

每个数据块的第一行包含三个整数 $n_i,l_i,r_i$ ( $1\le n_i\le 10^5,1\le l_i\le r_i\le c_{i,1}+\dots +c_{i,n_i}\le 10^{17}$ )( $1\le n_i\le 10^5,1\le l_i\le r_i\le c_{i,1}+\dots +c_{i,n_i}\le 10^{17}$ )-- $i$ /th 多集合中不同数字的个数，以及从 $i$ /th 多集合中添加到 $X$ 的元素个数限制。

代码块的第二行包含 $n_i$ 个整数 $a_{i,1},\dots ,a_{i,n_i}$ ( $1\le a_{i,1}<\dots <a_{i,n_i}\le 10^{17}$ ) - $i$ -th multiset 的不同元素。

第三行包含 $n_i$ 个整数 $c_{i,1},\dots ,c_{i,n_i}$ 。( $1\le c_{i,j}\le 10^{12}$ ) - $i$ /th多集合中元素的副本数。

保证所有测试用例的 $m$ 值之和不超过 $10^5$ ，所有测试用例的所有块的 $n_i$ 值之和也不超过 $10^5$ 。

输出

针对每个测试用例，输出多集合 $X$ 可能达到的最小反美度。

题目描述

Let’s define the anti-beauty of a multiset { b 1 , b 2 , … , b l e n } \{b_1, b_2, \ldots, b_{len}\} {b1?,b2?,…,blen?} as the number of occurrences of the number $len$ in the multiset.

You are given $m$ multisets, where the $i$ -th multiset contains $n_i$ distinct elements, specifically: $c_{i,1}$ copies of the number $a_{i,1}$ , $c_{i,2}$ copies of the number $a_{i,2},\dots ,c_{i,n_i}$ copies of the number $a_{i,n_i}$ . It is guaranteed that $a_{i,1}<a_{i,2}<\dots <a_{i,n_i}$ . You are also given numbers $l_1,l_2,\dots ,l_m$ and $r_1,r_2,\dots ,r_m$ such that $1\le l_i\le r_i\le c_{i,1}+\dots +c_{i,n_i}$ .

Let’s create a multiset $X$ , initially empty. Then, for each $i$ from $1$ to $m$ , you must perform the following action exactly once:

1. Choose some $v_i$ such that $l_i\le v_i\le r_i$
2. Choose any $v_i$ numbers from the $i$ -th multiset and add them to the multiset $X$ .

You need to choose $v_1,\dots ,v_m$ and the added numbers in such a way that the resulting multiset $X$ has the minimum possible anti-beauty.

输入格式

Each test consists of multiple test cases. The first line contains a single integer $t$ ( $1\le t\le 10^4$ ) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $m$ ( $1\le m\le 10^5$ ) — the number of given multisets.

Then, for each $i$ from $1$ to $m$ , a data block consisting of three lines is entered.

The first line of each block contains three integers $n_i,l_i,r_i$ ( $1\le n_i\le 10^5,1\le l_i\le r_i\le c_{i,1}+\dots +c_{i,n_i}\le 10^{17}$ ) — the number of distinct numbers in the $ i $ -th multiset and the limits on the number of elements to be added to $X$ from the $i$ -th multiset.

The second line of the block contains $n_i$ integers $a_{i,1},\dots ,a_{i,n_i}$ ( $1\le a_{i,1}<\dots <a_{i,n_i}\le 10^{17}$ ) — the distinct elements of the $i$ -th multiset.

The third line of the block contains $n_i$ integers $c_{i,1},\dots ,c_{i,n_i}$( $1\le c_{i,j}\le 10^{12}$ ) — the number of copies of the elements in the $i$ -th multiset.

It is guaranteed that the sum of the values of $m$ for all test cases does not exceed $10^5$ , and also the sum of $n_i$ for all blocks of all test cases does not exceed $10^5$ .

输出格式

For each test case, output the minimum possible anti-beauty of the multiset $X$ that you can achieve.

样例 #1

样例输入 #1

7
3
3 5 6
10 11 12
3 3 1
1 1 3
12
4
2 4 4
12 13
1 5
1
7 1000 1006
1000 1001 1002 1003 1004 1005 1006
147 145 143 143 143 143 142
1
2 48 50
48 50
25 25
2
1 1 1
1
1
1 1 1
2
1
1
1 1 1
1
2
2
1 1 1
1
1
2 1 1
1 2
1 1
2
4 8 10
11 12 13 14
3 3 3 3
2 3 4
11 12
2 2

样例输出 #1

1
139
0
1
1
0
0

提示

In the first test case, the multisets have the following form:

1. { 10 , 10 , 10 , 11 , 11 , 11 , 12 } \{10, 10, 10, 11, 11, 11, 12\} {10,10,10,11,11,11,12} . From this multiset, you need to select between $5$ and $6$ numbers.
2. { 12 , 12 , 12 , 12 } \{12, 12, 12, 12\} {12,12,12,12} . From this multiset, you need to select between $1$ and $3$ numbers.
3. { 12 , 13 , 13 , 13 , 13 , 13 } \{12, 13, 13, 13, 13, 13\} {12,13,13,13,13,13} . From this multiset, you need to select $4$ numbers.

You can select the elements { 10 , 11 , 11 , 11 , 12 } \{10, 11, 11, 11, 12\} {10,11,11,11,12} from the first multiset, { 12 } \{12\} {12} from the second multiset, and { 13 , 13 , 13 , 13 } \{13, 13, 13, 13\} {13,13,13,13} from the third multiset. Thus, X = { 10 , 11 , 11 , 11 , 12 , 12 , 13 , 13 , 13 , 13 } X = \{10, 11, 11, 11, 12, 12, 13, 13, 13, 13\} X={10,11,11,11,12,12,13,13,13,13} . The size of $X$ is $10$ , the number $10$ appears exactly $1$ time in $X$ , so the anti-beauty of $X$ is $1$ . It can be shown that it is not possible to achieve an anti-beauty less than $1$ .

$以上来自CodeForces，翻译工具DeepL$

解题思路

暴力思想：我们枚举每一个数字 $x$，让最终选的数字数量等同于 $x$，使 $x$ 选的尽量少。

这个问题我们只需要每次对所有多重集选除 $x$ 外的所有数，如果选的数仍然小于 $l$ 那再选 $x$，选完所有多重集后，如果选的数仍然数量小于 $x$，那么剩下的数我们明显都只能选 $x$ 了，如果大于等于了 $x$，那么答案就是我们已经选了的 $x$ 的个数。

当然，当 $\Sigma l_i\le x\le \Sigma r_i$ 时以上结论才成立，否则这个数不可能作为答案出现。对于一个集合没有 $x$，我们还要将强制选上 $r$ 个，这样时间复杂度会退化到 $O(n\times m)$，不正确。

如何解决？我们不记录我们总共选了多少个，记录我们会少选多少个数字，因为只有当 $x$ 出现在一个集合时才会出现我不选 $r$ 个的可能性。

那么我们就用 map 来记录我们选了多少个 $x$ 和在尽量少选 $x$ 的可能下`最少少选了几个数，最后枚举 $\Sigma l_i$ 到 $\Sigma r_i$ 的所有数字的贡献即可，如果一个数在这区间没有出现，明显答案就为 $0$，此时可以跳出枚举，这样保证枚举数量为 $O(n)$。时间复杂度：$O((n+m)\times \log n)$。

最后 $Answer$ 取最小值，就是最终答案。注意程序中变量赋初值。

AC Code

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define mp map
#define ii int,int
const int Maxn = 1e5 + 5;
int m, len[Maxn], l[Maxn], r[Maxn], a[Maxn], c[Maxn];
mp<ii>arr1, arr2, arr3;
int ans;
inline void solve() {
	arr1.clear();
	arr2.clear();
	arr3.clear();
	cin >> m;
	int tot1 = 0, tot2 = 0, sum, tmp, x, y;
	for (int i = 1; i <= m; i++) {
		cin >> len[i] >> l[i] >> r[i];
		sum = 0;
		for (int j = 1; j <= len[i]; j++) {
			cin >> a[j];
			arr3[a[j]] = 1;
		}
		for (int j = 1; j <= len[i]; j++) {
			cin >> c[j];
			sum += c[j];
		}
		for (int j = 1; j <= len[i]; j++) {
			tmp = max(0ll, (l[i] - (sum - c[j])));
			arr1[a[j]] += tmp;
			arr2[a[j]] -= r[i] - min(r[i], max(l[i], sum - c[j]));
		}
		tot1 += r[i];
		tot2 += l[i];
	}
	ans = LONG_LONG_MAX;
	for (int i = tot2; i <= tot1; i++) {
		if (!arr3[i]) {
			ans = 0;
			break;
		}
		x = i, y = arr1[i];
		tmp = -arr2[x];
		if (tot1 - tmp >= x) {
			ans = min(ans, y);
		} else {
			ans = min(ans, y + x - (tot1 - tmp));
		}
	}
	cout << ans << endl;
}
inline void work() {
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
}
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	work();
	return 0;
}

最后推荐一个 $CodeForces$ 翻译插件：CodeForcesBetter。