小蓝鲸的鱿鱼游戏

小蓝鲸的鱿鱼游戏

一、题目要求

小蓝鲸们在一起做游戏，要从起点乘车到达终点。

在起点和终点之间，有两辆用于传送的列车A和B，车票的价格分别是a枚金币和b枚金币。

每个小蓝鲸手里都有若干枚金币p_i，但他们不被允许独自登车，而是必须寻找一位搭档，这位搭档的金币数必须是a - p_i或者b - p_i，这样一起凑齐恰好a枚或者b枚金币，两人方可被允许乘坐对应的列车A或B前往终点，否则会留在起点被鱿鱼吃掉。

比较特殊的是，如果有小蓝鲸手中金币数p_i恰好满足a - p_i = p_i或b - p_i = p_i，小蓝鲸将被判定为自己与自己组队成功，他也能成功乘车离开。

请你帮忙判断，在这局游戏中，是否所有小蓝鲸都能成功逃脱呢？

提示：可以采用一个并查集把可能配对的小蓝鲸并在一起，同时给每个小蓝鲸标记是通过A列车并在一起还是通过B列车并一起，最后结合标记和并查集再思考把每个小蓝鲸划分到哪辆列车,还是不能划分。时间复杂度为O(n)O(n)
Input
第一行包含三个整数n, a, b (1  <= n <= 10^5; 1  <= a, b <= 10^9)，以空格分隔。并且保证a != b。

下一行包含n个互不相同的整数p_1, p_2, …, p_n(1 <= p_i <= 10^9)，代表每个小蓝鲸手中的金币数量，以空格分隔。

Output
如果可以成功逃脱，则输出两行，第一行输出1，下一行输出每个小蓝鲸乘坐的列车编号：若乘坐A列车则输出0，若乘坐B列车则输出1，以空格隔开；

如果不是所有小蓝鲸都能成功离开，只输出一行，输出0。（行尾都没有多余的空格）

样例
输入1

4 5 9
2 3 4 5
输出1

1
0 0 1 1
输入2

3 3 4
1 2 4
输出1

0
备注:可能所有小蓝鲸都乘坐一辆列车离开，而另一辆列车为空。

二、 代码实现

#include <iostream>
using namespace std;

int main()
{
	int n;
	int  a, b;
   cout<<"输入n，a，b"<<endl;
	n=4;
	a=5;
	b=9;
	// cin>>n>>a>>b;
	
	cout<<n<<endl<<a<<endl<<b<<endl;
	
	int *p = (int*)malloc(sizeof(int)*n);
	int *q = (int*)malloc(sizeof(int)*n);
	for(int j=0;j<n;j++)
	{
		q[j] = -1;
	}
	
	//for(int j=0;j<n;j++){cin>>p[j];}
	p[0] = 2;
	p[1] = 3;
	p[2] = 4;
	p[3] = 5;
	
	if(a % 2 == 0)
	{
		for(int j=0;j<n;j++)
		{
			if(p[j] == a / 2){q[j] = 0;}
		}
	}
	if(b % 2 == 0)
	{
		for(int j=0;j<n;j++)
		{
			if(p[j] == b / 2){q[j] = 0;}
		}
	}
	// 特殊情况
	
	for(int m=0;m<n;m++)
	{
		if(q[m] != -1){continue;}
		for(int t =m+1 ;t<n;t++){
			if(q[t] != -1){continue;}
			if(p[m] + p[t] == a){
				q[m]=0;
				q[t]=0;
				
				break; // 不能下往下检查了
			}
			if(p[m] + p[t] == b){
				q[m]=1;
				q[t]=1;
				
				break;
			}
		}	
	}
	// 一般情况
	
	int success = 1;
	for(int j=0;j<n;j++){
		if(q[j] == -1){
			success = 0;
			break;
		}
	}
	// 判断是不是全都坐上车了
	cout<<"输出：";
	if(success){
		cout<<1<<endl;
		for(int j=0;j<n;j++){
			cout<<q[j];
		}
	}else{
		cout<<0;
	}
	//  cout<<q[0]<<q[1]<<q[2]<<q[3];
	
	
}