Problem
题目简述
-
两个序列 \(A, B\)。这两个序列都是由 \(0,1,2\) 这三个数构成。
-
\(x_1,y_1,z_1\) 和 \(x_2,y_2,z_2\) 分别代表 \(A\) 序列和 \(B\) 序列中 \(0,1,2\) 出现的次数。
-
你可以重新排列两个序列中的元素，然后生成一个新序列 \(C\)，\(C\) 的生成规则如下：
\[C_i = \begin{cases}A_iB_i &A_i>B_i \\
0&A_i = B_i\\ -A_iB_i &A_i<B_i\end{cases}\]
求：所有排列的方案中，\(C\) 序列所有元素之和的最大值。
思路
本题采用的算法：贪心、构造。
- 尽量地凑出 \((A_i,B_i)\) 为 \((2,1)\)。
- \(B_i=2\)，则和 \(A_i=0\) 的情况配对。
- 对于剩下的元素，把相同的元素配对。
代码
#include <bits/stdc++.h>
using namespace std;
int t;
int main() {
scanf("%d", &t);
int x1, y1, z1, x2, y2, z2;
while (t--) {
scanf("%d%d%d%d%d%d", &x1, &y1, &z1, &x2, &y2, &z2);
x1 -= min(x1, z2), z2 -= min(x1, z2);
z1 -= min(z1, z2), z2 -= min(z1, z2);
int ans = (min(y2, z1) - min(y1, z2)) << 1;
printf("%d\n", ans);
}
return 0;
}