Codeforces Round #673 (Div. 2) B. Two Arrays(思维,构造)
程序员文章站
2022-06-05 13:09:16
...
题意:
给你一个长n的数组a,给一个T,定义f(x)为x数组中
a
i
+
a
j
=
=
T
(
i
<
j
)
a_i+a_j==T(i<j)
ai+aj==T(i<j)的数组对数,将a数组分成c,d俩个数组,在俩数组中存数字,使得
f
(
c
)
+
f
(
d
)
f(c)+f(d)
f(c)+f(d)的值最小
题解:
遍历一遍数组,若
T
−
a
i
T-a_i
T−ai在第一个数组中已经有了,则判断第一个和第二个数组中谁的数量多,将其放入数量最少的数组中,若第一个数组中
T
−
a
i
T-a_i
T−ai不存在,直接将
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 Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)
-
构造思维+树形结构 Codeforces Round #612 (Div. 2) D题 Numbers on Tree
-
Codeforces Round #657 (Div. 2) B. Dubious Cyrpto(思维,数学)
-
Codeforces Round #673 (Div. 2) B. Two Arrays(思维,构造)
-
B. Two Arrays(模拟+思维)Codeforces Round #673 (Div. 2)
-
B. Jzzhu and Sequences(思维)Codeforces Round #257 (Div. 2)
-
Codeforces Raif Round 1 (Div. 1 + Div. 2) D. Bouncing Boomerangs(思维+构造)
-
Codeforces Round #621 (Div. 1 + Div. 2) B. Cow and Friend (思维)
-
Educational Codeforces Round 50 (Rated for Div. 2) D. Vasya and Arrays(前缀和,思维)
-
Codeforces Round #649 (Div. 2)-B. Most socially-distanced subsequence(思维)