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