CF1893C Freedom of Choice 题解

发布时间:2024年01月22日

Freedom of Choice

传送门

题面翻译

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

我们给出了 m m m 个多集,其中 i i i 个多集包含 n i n_i ni? 个不同的元素,具体来说就是:数字 a i , 1 a_{i,1} ai,1? c i , 1 c_{i, 1} ci,1? 个副本,数字 a i , 2 , … , c i , n i a_{i,2}, \ldots, c_{i, n_i} ai,2?,,ci,ni?? c i , 2 c_{i, 2} ci,2? 个副本,数字 a i , n i a_{i, n_i} ai,ni?? a i , 2 , … , c i , n i a_{i,2}, \ldots, c_{i, n_i} ai,2?,,ci,ni?? 个副本。可以保证 a i , 1 < a i , 2 < … < a i , n i a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i} ai,1?<ai,2?<<ai,ni?? 。还给出了数字 l 1 , l 2 , … , l m l_1, l_2, \ldots, l_m l1?,l2?,,lm? r 1 , r 2 , … , r m r_1, r_2, \ldots, r_m r1?,r2?,,rm? ,使得 1 ≤ l i ≤ r i ≤ c i , 1 + … + c i , n i 1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i} 1li?ri?ci,1?++ci,ni?? .

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

  1. 选择某个 v i v_i vi? ,使得 l i ≤ v i ≤ r i l_i \le v_i \le r_i li?vi?ri? 为空
  2. i i i /th多集合中选择任意 v i v_i vi? 个数字,并将它们添加到多集合 X X X 中。

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

输入

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

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

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

每个数据块的第一行包含三个整数 n i , l i , r i n_i, l_i, r_i ni?,li?,ri? ( 1 ≤ n i ≤ 1 0 5 , 1 ≤ l i ≤ r i ≤ c i , 1 + … + c i , n i ≤ 1 0 17 1 \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} 1ni?105,1li?ri?ci,1?++ci,ni??1017 )( 1 ≤ n i ≤ 1 0 5 , 1 ≤ l i ≤ r i ≤ c i , 1 + … + c i , n i ≤ 1 0 17 1 \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} 1ni?105,1li?ri?ci,1?++ci,ni??1017 )-- i i i /th 多集合中不同数字的个数,以及从 i i i /th 多集合中添加到 X X X 的元素个数限制。

代码块的第二行包含 n i n_i ni? 个整数 a i , 1 , … , a i , n i a_{i, 1}, \ldots, a_{i, n_i} ai,1?,,ai,ni?? ( 1 ≤ a i , 1 < … < a i , n i ≤ 1 0 17 1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17} 1ai,1?<<ai,ni??1017 ) - i i i -th multiset 的不同元素。

第三行包含 n i n_i ni? 个整数 c i , 1 , … , c i , n i c_{i, 1}, \ldots, c_{i, n_i} ci,1?,,ci,ni?? 。( 1 ≤ c i , j ≤ 1 0 12 1 \le c_{i, j} \le 10^{12} 1ci,j?1012 ) - i i i /th多集合中元素的副本数。

保证所有测试用例的 m m m 值之和不超过 1 0 5 10^5 105 ,所有测试用例的所有块的 n i n_i ni? 值之和也不超过 1 0 5 10^5 105

输出

针对每个测试用例,输出多集合 X X 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 l e n len len in the multiset.

You are given m m m multisets, where the i i i -th multiset contains n i n_i ni? distinct elements, specifically: c i , 1 c_{i, 1} ci,1? copies of the number a i , 1 a_{i,1} ai,1? , c i , 2 c_{i, 2} ci,2? copies of the number a i , 2 , … , c i , n i a_{i,2}, \ldots, c_{i, n_i} ai,2?,,ci,ni?? copies of the number a i , n i a_{i, n_i} ai,ni?? . It is guaranteed that a i , 1 < a i , 2 < … < a i , n i a_{i, 1} < a_{i, 2} < \ldots < a_{i, n_i} ai,1?<ai,2?<<ai,ni?? . You are also given numbers l 1 , l 2 , … , l m l_1, l_2, \ldots, l_m l1?,l2?,,lm? and r 1 , r 2 , … , r m r_1, r_2, \ldots, r_m r1?,r2?,,rm? such that 1 ≤ l i ≤ r i ≤ c i , 1 + … + c i , n i 1 \le l_i \le r_i \le c_{i, 1} + \ldots + c_{i, n_i} 1li?ri?ci,1?++ci,ni?? .

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

  1. Choose some v i v_i vi? such that l i ≤ v i ≤ r i l_i \le v_i \le r_i li?vi?ri?
  2. Choose any v i v_i vi? numbers from the i i i -th multiset and add them to the multiset X X X .

You need to choose v 1 , … , v m v_1, \ldots, v_m v1?,,vm? and the added numbers in such a way that the resulting multiset X X X has the minimum possible anti-beauty.

输入格式

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

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

Then, for each i i i from 1 1 1 to m m 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 n_i, l_i, r_i ni?,li?,ri? ( 1 ≤ n i ≤ 1 0 5 , 1 ≤ l i ≤ r i ≤ c i , 1 + … + c i , n i ≤ 1 0 17 1 \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} 1ni?105,1li?ri?ci,1?++ci,ni??1017 ) — the number of distinct numbers in the $ i $ -th multiset and the limits on the number of elements to be added to X X X from the i i i -th multiset.

The second line of the block contains n i n_i ni? integers a i , 1 , … , a i , n i a_{i, 1}, \ldots, a_{i, n_i} ai,1?,,ai,ni?? ( 1 ≤ a i , 1 < … < a i , n i ≤ 1 0 17 1 \le a_{i, 1} < \ldots < a_{i, n_i} \le 10^{17} 1ai,1?<<ai,ni??1017 ) — the distinct elements of the i i i -th multiset.

The third line of the block contains n i n_i ni? integers c i , 1 , … , c i , n i c_{i, 1}, \ldots, c_{i, n_i} ci,1?,,ci,ni??( 1 ≤ c i , j ≤ 1 0 12 1 \le c_{i, j} \le 10^{12} 1ci,j?1012 ) — the number of copies of the elements in the i i i -th multiset.

It is guaranteed that the sum of the values of m m m for all test cases does not exceed 1 0 5 10^5 105 , and also the sum of n i n_i ni? for all blocks of all test cases does not exceed 1 0 5 10^5 105 .

输出格式

For each test case, output the minimum possible anti-beauty of the multiset X X 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 5 5 and 6 6 6 numbers.
  2. { 12 , 12 , 12 , 12 } \{12, 12, 12, 12\} {12,12,12,12} . From this multiset, you need to select between 1 1 1 and 3 3 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 4 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 X X is 10 10 10 , the number 10 10 10 appears exactly 1 1 1 time in X X X , so the anti-beauty of X X X is 1 1 1 . It can be shown that it is not possible to achieve an anti-beauty less than 1 1 1 .

以上来自 C o d e F o r c e s ,翻译工具 D e e p L 以上来自CodeForces,翻译工具DeepL 以上来自CodeForces,翻译工具DeepL

解题思路

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

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

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

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

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

最后 A n s w e r Answer 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;
}

最后推荐一个 C o d e F o r c e s CodeForces CodeForces 翻译插件:CodeForcesBetter

文章来源:https://blog.csdn.net/BestMonkey/article/details/135740693
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。