codeforces|Codeforces Round #665 (Div. 2) B. Ternary Sequence codeforces|算法

Title
CodeForces 1401 B. Ternary Sequence
Time Limit
2 seconds
Memory Limit
256 megabytes
Problem Description
You are given two sequencesa 1 , a 2 , … , a n a_1, a_2, \dots, a_n a1?,a2?,…,an? andb 1 , b 2 , … , b n b_1, b_2, \dots, b_n b1?,b2?,…,bn?. Each element of both sequences is either0 0 0,1 1 1 or2 2 2. The number of elements0 0 0,1 1 1,2 2 2 in the sequencea a a isx 1 x_1 x1?,y 1 y_1 y1?,z 1 z_1 z1? respectively, and the number of elements0 0 0,1 1 1,2 2 2 in the sequenceb b b isx 2 x_2 x2?,y 2 y_2 y2?,z 2 z_2 z2? respectively.
You can rearrange the elements in both sequencesa a a andb b b however you like. After that, let’s define a sequencec c c as follows:
c i = { a i b iifa i > b i 0ifa i = b i ? a i b iifa i < b i c_{i}=\left\{\begin{array}{ll} a_{i} b_{i} & \text { if } a_{i}>b_{i} \\ 0 & \text { if } a_{i}=b_{i} \\ -a_{i} b_{i} & \text { if } a_{i}bi? if ai?=bi? if ai? You’d like to make∑ i = 1 n c i \sum_{i=1}^n c_i ∑i=1n?ci? (the sum of all elements of the sequencec c c) as large as possible. What is the maximum possible sum?
Input
The first line contains one integert t t ( 1 ≤ t ≤ 1 0 4 1 \le t \le 10^4 1≤t≤104) — the number of test cases.
Each test case consists of two lines. The first line of each test case contains three integersx 1 x_1 x1?,y 1 y_1 y1?,z 1 z_1 z1? ( 0 ≤ x 1 , y 1 , z 1 ≤ 1 0 8 0 \le x_1, y_1, z_1 \le 10^8 0≤x1?,y1?,z1?≤108) — the number of0 0 0-s,1 1 1-s and2 2 2-s in the sequencea a a.
The second line of each test case also contains three integersx 2 x_2 x2?,y 2 y_2 y2?,z 2 z_2 z2? ( 0 ≤ x 2 , y 2 , z 2 ≤ 1 0 8 0 \le x_2, y_2, z_2 \le 10^8 0≤x2?,y2?,z2?≤108; x 1 + y 1 + z 1 = x 2 + y 2 + z 2 > 0 x_1 + y_1 + z_1 = x_2 + y_2 + z_2 > 0 x1?+y1?+z1?=x2?+y2?+z2?>0) — the number of0 0 0-s,1 1 1-s and2 2 2-s in the sequenceb b b.
Output
For each test case, print the maximum possible sum of the sequencec c c.
Sample Input

3 2 3 2 3 3 1 4 0 1 2 3 0 0 0 1 0 0 1

Sample Onput

4 2 0

Note
In the first sample, one of the optimal solutions is:
a = { 2 , 0 , 1 , 1 , 0 , 2 , 1 } a = \{2, 0, 1, 1, 0, 2, 1\} a={2,0,1,1,0,2,1}
b = { 1 , 0 , 1 , 0 , 2 , 1 , 0 } b = \{1, 0, 1, 0, 2, 1, 0\} b={1,0,1,0,2,1,0}
c = { 2 , 0 , 0 , 0 , 0 , 2 , 0 } c = \{2, 0, 0, 0, 0, 2, 0\} c={2,0,0,0,0,2,0}
In the second sample, one of the optimal solutions is:
a = { 0 , 2 , 0 , 0 , 0 } a = \{0, 2, 0, 0, 0\} a={0,2,0,0,0}
b = { 1 , 1 , 0 , 1 , 0 } b = \{1, 1, 0, 1, 0\} b={1,1,0,1,0}
c = { 0 , 2 , 0 , 0 , 0 } c = \{0, 2, 0, 0, 0\} c={0,2,0,0,0}
In the third sample, the only possible solution is:
a = { 2 } a = \{2\} a={2}
b = { 2 } b = \{2\} b={2}
c = { 0 } c = \{0\} c={0}
Source
CodeForces 1401 B. Ternary Sequence
题意给出ab两个数组0,1,2的数量
c i = { a i b iifa i > b i 0ifa i = b i ? a i b iifa i < b i c_{i}=\left\{\begin{array}{ll} a_{i} b_{i} & \text { if } a_{i}>b_{i} \\ 0 & \text { if } a_{i}=b_{i} \\ -a_{i} b_{i} & \text { if } a_{i}bi? if ai?=bi? if ai? 随意组合求C的最大值
思路贪心的想
只有 a 2 配 b 1 a_2配b_1 a2?配b1?是 2 2 2a 1 配 b 2 a_1配b_2 a1?配b2?是 ? 2 -2 ?2 其余都是 0 0 0
【codeforces|Codeforces Round #665 (Div. 2) B. Ternary Sequence】于是先把 b 1 b_1 b1?分配给 a 2 a_2 a2? 再用其余的去填充 b 2 b_2 b2? 最后无可奈何再减去 a 1 配 b 2 a_1配b_2 a1?配b2?
AC代码:

#include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; const int maxn = 3e5 + 5; const ll inf = 0x3f3f3f3f; const ll mod = 1e9 + 7; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend()int main() { ios::sync_with_stdio(false); cin.tie(0), cout.tie(0); int T; cin >> T; while (T--) { vector a(3), b(3); for (auto &it : a) cin >> it; for (auto &it : b) cin >> it; ll mini = min(a[2], b[1]); ll ans = 0; ans += mini * 2; a[2] -= mini, b[1] -= mini; mini = min(a[2], b[2]); a[2] -= mini, b[2] -= mini; mini = min(a[0], b[2]); a[0] -= mini, b[2] -= mini; mini = min(a[1], b[2]); cout << ans - 2 * mini << endl; } return 0; }