B. Two Arrays(思维+贪心分配)

93 阅读 0 评论 62 点赞

我是靠谱客的博主乐观大象，最近开发中收集的这篇文章主要介绍B. Two Arrays(思维+贪心分配)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

https://codeforces.com/contest/1417/problem/B

思路：感觉理论上是可以map搞出来的。

贪心考虑，对于序列里的一个数，如果这个数>T/2,会发现全部扔到黑色里面可以保证里面一个都不会有出现相加和为T的。如果这个数<T/2,全部扔到白色里面去，同理严格小于T/2的时候也是相加和不为T的。比如T=7,T/2=3.严格小于的比如3+3是不会到的。

剩下考虑==T/2的情况。

比如4 T=4

2 2 2 2

手动发现要一个扔白一个扔偶是最佳的，也就是平均分配使得总对数之和最小。（类似不等式）

剩下如果T%2!=0的话，直接扔白色的就好了。例子就是样例1.

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+100;
typedef long long LL;
LL a[maxn];
bool vis[maxn];
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
  LL t;cin>>t;
  while(t--)
  {
  	LL n,k;cin>>n>>k;
  	for(LL i=0;i<=n+10;i++) a[i]=vis[i]=0;
  	for(LL i=1;i<=n;i++) cin>>a[i];
  	LL num=0;
  	for(LL i=1;i<=n;i++)
  	{
  		if(a[i]>k/2) vis[i]=1;
		else if(a[i]<k/2) vis[i]=0;
		else if(a[i]==k/2&&k%2!=0)
		{
			vis[i]=0;
		}
		else if(a[i]==k/2&&k%2==0)
		{
			if(num&1) vis[i]=1,num++;
			else if(num%2==0) vis[i]=0,num++;
		}  	
	}
	for(LL i=1;i<=n;i++)
	{
		if(vis[i]==1) cout<<0<<" ";
		else cout<<1<<" ";
	}
	cout<<endl;
  }
return 0;
}