CF1893C Freedom of Choice 题解

2024-01-23 08:54:02
开发
29

Freedom of Choice

传送门

题面翻译

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

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

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

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

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

输入

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

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

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

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

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

第三行包含 $n_i$ 个整数 $c_{i, 1}, \ldots, c_{i, n_i}$ 。( $\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, \ldots, b_{len}\}$ as the number of occurrences of the number $l e n$ 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}, \ldots, c_{i, n_i}$ copies of the number $a_{i, n_i}$ . It is guaranteed that $a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i}$ . You are also given numbers $l_1, l_2, \ldots, l_m$ and $r_1, r_2, \ldots, r_m$ such that $\le l_i \le r_i \le c_{i, 1} + \ldots + 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:

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

You need to choose $v_1, \ldots, 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$ ( $\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$ ( $\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$ ( $\le n_i \le 10^5, 1 \le l_i \le r_i \le c_{i, 1} + \ldots + 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}, \ldots, a_{i, n_i}$ ( $\le a_{i, 1} < \ldots < 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}, \ldots, c_{i, n_i}$ ( $\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

提示

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

${10, 10, 10, 11, 11, 11, 12\}$ . From this multiset, you need to select between $5$ and $6$ numbers.
${12, 12, 12, 12\}$ . From this multiset, you need to select between $1$ and $3$ numbers.
${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\}$ from the first multiset, ${12\}$ from the second multiset, and ${13, 13, 13, 13\}$ from the third multiset. Thus, $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$ .

$以上来自 C o d e F orces ，翻译工具 Dee p L$

解题思路

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

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

当然，当 $\Sigma l_i≤x≤\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})$ 。

最后 $A n s w er$ 取最小值，就是最终答案。注意程序中变量赋初值。

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;
}

最后推荐一个 $C o d e F orces$ 翻译插件：CodeForcesBetter。

原文地址:https://blog.csdn.net/BestMonkey/article/details/135740693 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：https://www.suanlizi.com/kf/1749596312850010112.html 如若内容造成侵权/违法违规/事实不符，请联系《酸梨子》网邮箱：1419361763@qq.com进行投诉反馈，一经查实，立即删除！

阅读全部