欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Codeforces Round #673 (Div. 2) B. Two Arrays(思维,构造)

程序员文章站 2022-06-05 13:09:16
...

Codeforces Round #673 (Div. 2) B. Two Arrays(思维,构造)

题意
给你一个长n的数组a,给一个T,定义f(x)为x数组中 a i + a j = = T ( i < j ) a_i+a_j==T(i<j) ai+aj==Ti<j的数组对数,将a数组分成c,d俩个数组,在俩数组中存数字,使得 f ( c ) + f ( d ) f(c)+f(d) f(c)+f(d)的值最小
题解
遍历一遍数组,若 T − a i T-a_i Tai在第一个数组中已经有了,则判断第一个和第二个数组中谁的数量多,将其放入数量最少的数组中,若第一个数组中 T − a i T-a_i Tai不存在,直接将 a i a_i ai放入第一个中即可
code:

#include<bits/stdc++.h>
 
#pragma GCC optimize(2)
#define rep(i,a,n) for (int i=a;i<=n;i++)//i为循环变量,a为初始值,n为界限值,递增
#define per(i,a,n) for (int i=a;i>=n;i--)//i为循环变量, a为初始值,n为界限值,递减。
 
using namespace std;
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0)
#define ll long long
#define ull unsigned long long
#define ld long double
const int INF = 0x3f3f3f3f;
const ll LINF = 1ll<<60;
const int mod=1e9+7;
 
ll read()//快读
{
	ll w = 1, s = 0;
	char ch = getchar();
	while (ch < '0' || ch>'9') { if (ch == '-') w = -1; ch = getchar(); }
	while (ch >= '0' && ch <= '9') { s = s * 10 + ch - '0';    ch = getchar(); }
	return s * w;
}
void solve(){
	ll n,t,a[100010];
	map<ll,ll> mp1;
	map<ll,ll> mp2;
	cin>>n>>t;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n){
		if(mp1[t-a[i]]>0){
			if(mp1[t-a[i]]>mp2[t-a[i]]){
				mp2[a[i]]++;
				a[i]=1;
			}
			else {
				mp1[a[i]]++;
				a[i]=0;
			}
		}
		else {
			mp1[a[i]]++;
			a[i]=0;
		}
	}
	rep(i,1,n) cout<<a[i]<<" ";
	cout<<endl;
 
}
 
int main(){
	int _;
	cin>>_;
	while(_--) solve();
    return 0;
}
相关标签: codeforces