CF1401B Ternary Sequence
题目描述
给定两个序列 \(a_1, a_2, \dots, a_n\) 和 \(b_1, b_2, \dots, b_n\),每个序列中的元素都是 \(0\), \(1\) 或 \(2\)。序列 \(a\) 中 \(0\), \(1\), \(2\) 的个数分别为 \(x_1\), \(y_1\), \(z_1\),序列 \(b\) 中 \(0\), \(1\), \(2\) 的个数分别为 \(x_2\), \(y_2\), \(z_2\)。
你可以任意重新排列序列 \(a\) 和 \(b\) 的元素。之后,定义序列 \(c\) 如下:
你希望使 \(\sum_{i=1}^n c_i\)(即序列 \(c\) 所有元素之和)尽可能大。请问最大可能的和是多少?
输入格式
第一行包含一个整数 \(t\)(\(1 \le t \le 10^4\)),表示测试用例的数量。
每个测试用例包含两行。每个测试用例的第一行包含三个整数 \(x_1, y_1, z_1\)(\(0 \le x_1, y_1, z_1 \le 10^8\)),分别表示序列 \(a\) 中 \(0\), \(1\), \(2\) 的个数。
每个测试用例的第二行也包含三个整数 \(x_2, y_2, z_2\)(\(0 \le x_2, y_2, z_2 \le 10^8\),且 \(x_1 + y_1 + z_1 = x_2 + y_2 + z_2 > 0\)),分别表示序列 \(b\) 中 \(0\), \(1\), \(2\) 的个数。
输出格式
对于每个测试用例,输出一个整数,表示序列 \(c\) 的最大可能和。
思路
- 先把c的各种取值情况分析一下,如下表:
a | b | c | ||
---|---|---|---|---|
a > b | 2 | 1 | 2 | 使之尽可能多 |
2 | 0 | 0 | ||
1 | 0 | 0 | ||
a = b | 2 | 2 | 0 | |
1 | 1 | 0 | ||
0 | 0 | 0 | ||
a < b | 1 | 2 | -2 | 使之尽可能少 |
0 | 1 | 0 | ||
0 | 2 | 0 |
- 思路:希望使 \(\sum_{i=1}^n c_i\)(即序列 \(c\) 所有元素之和)尽可能大。即:使(a,b)=(2,1)最多,使(a,b)=(1,2)最少
0 | 1 | 2 | |
---|---|---|---|
a | x | y | z |
b | xx | yy | zz |
- 如何实现:使(a,b)=(2,1)最多,使(a,b)=(1,2)最少?
(1)使(a,b)=(1,2)最少:先用x消耗zz
(2)如果没有x消耗完zz,就用z消耗zz
(3)最后的答案就是剩余的(2,1)-(1,2)的个数的两倍,即2 * (min(z, yy) - min(y, zz))
AC代码
#include <bits/stdc++.h>
using namespace std;signed main()
{ios::sync_with_stdio(false);cin.tie(0);int t;cin >> t;while (t--){int x, y, z, xx, yy, zz, a, b;cin >> x >> y >> z >> xx >> yy >> zz;a = min(x, zz);x -= a;zz -= a;b = min(z, zz);z -= b;zz -= b;cout << 2 * (min(z, yy) - min(y, zz)) << '\n';}
}