CodeForces 1401B Ternary Sequence （贪心）

最新推荐文章于 2025-04-05 20:09:30 发布

masterwater

最新推荐文章于 2025-04-05 20:09:30 发布

阅读量282

点赞数

分类专栏：贪心数论

本文链接：https://blog.csdn.net/masterwater/article/details/108224632

版权

数论同时被 2 个专栏收录

16 篇文章

订阅专栏

贪心

8 篇文章

订阅专栏

本文探讨了一种通过重新排列两个包含0、1、2元素的序列来最大化配对后序列总和的算法策略。关键在于优先匹配特定元素以获得正收益，避免负收益，最终实现最优解。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

You are given two sequences a1,a2,…,ana1,a2,…,an and b1,b2,…,bnb1,b2,…,bn. Each element of both sequences is either 00, 11 or 22. The number of elements 00, 11, 22 in the sequence aa is x1x1, y1y1, z1z1 respectively, and the number of elements 00, 11, 22 in the sequence bb is x2x2, y2y2, z2z2 respectively.

You can rearrange the elements in both sequences aa and bb however you like. After that, let's define a sequence cc as follows:

ci=⎧⎩⎨aibi0−aibiif ai>biif ai=biif ai<bici={aibiif ai>bi0if ai=bi−aibiif ai<bi

You'd like to make ∑ni=1ci∑i=1nci (the sum of all elements of the sequence cc) as large as possible. What is the maximum possible sum?

Input

The first line contains one integer tt (1≤t≤1041≤t≤104) — the number of test cases.

Each test case consists of two lines. The first line of each test case contains three integers x1x1, y1y1, z1z1 (0≤x1,y1,z1≤1080≤x1,y1,z1≤108) — the number of 00-s, 11-s and 22-s in the sequence aa.

The second line of each test case also contains three integers x2x2, y2y2, z2z2 (0≤x2,y2,z2≤1080≤x2,y2,z2≤108; x1+y1+z1=x2+y2+z2>0x1+y1+z1=x2+y2+z2>0) — the number of 00-s, 11-s and 22-s in the sequence bb.

Output

For each test case, print the maximum possible sum of the sequence cc.

Example

input

Copy

output

Copy

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}

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}

In the second sample, one of the optimal solutions is:

a={0,2,0,0,0}a={0,2,0,0,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}

In the third sample, the only possible solution is:

a={2}a={2}

b={2}b={2}

c={0}

题解：容易想到，数组a中的2只有与b中的1搭配才有正收益，a中的1和b中的1或0搭配才能避免负收益，其余搭配都是零收益。因此考虑贪心，即将数组a中的2与b中的1配对，再将a中的1和b中的0和1配对，最后计算a、b剩余的1 2配对产生的负收益。其余搭配不对结果产生影响，因此不考虑。

代码：

#include<iostream>
#include<cstdlib>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
int a[3],b[3],c[3];
bool flag[3];
int ans;

int calc()
{
	int sum=0,kk;
	kk=min(a[2],b[1]);
	sum+=2*kk;
	a[2]-=kk;b[1]-=kk;
	kk=min(a[0],b[2]);
	a[0]-=kk;b[2]-=kk;
	kk=min(a[2],b[2]);
	a[2]-=kk;b[2]-=kk;
	kk=min(a[1],b[2]);
	sum-=kk*2;
	return(sum);
}

int main()
{
	int n;
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		for (int j=0;j<=2;j++)	cin>>a[j];
		for (int j=0;j<=2;j++)	cin>>b[j];
		ans=calc();
		cout<<ans<<endl;
	}
}