【codeforces 746E】Numbers Exchange

青野

　　【题目链接】:http://codeforces.com/problemset/problem/746/E
　　【题意】



你有n张卡片,上面写着不同的数字;

然后另外一个人有m张上面写着不同的数字的卡片:卡片上的数字从1..m;

你可以和另外一个人交换卡片;

问你最少的交换次数;

使得你的n张卡片里面,卡片上的数字为奇数的和卡片上的数字为偶数的张数相同.

且这n张卡片不能有相同的数字;


　　【题解】



首先考虑去重的工作;

在去重之前;先算出;

原来的n张卡片里面,卡片上的数字是奇数的数字个数odd;

然后两个变量nexto和nexte分别表示下一个没被交换的奇数和偶数(1..m里面);

对于重复出现的卡片;

看看odd和n/2的关系;

如果

①

odd>n/2

则不能再来奇数了,所以只能拿一张偶数的和它交换(不管重复的这张的奇偶性);

(只是如果是奇数的,则奇数张数递减);

②

odd==n/2

则拿一张和这个数字奇偶性相同的卡片来交换;

③

odd< n/2

则不能来偶数了,需要拿一张奇数的卡片和它交换(仍旧不管重复的这张的奇偶性如何,都是拿一张奇数的)

这张重复的是偶数的话,odd++;

去重结束之后;

再根据odd和n/2的关系大小贪心换每一个数字;

如果

①odd< n/2

且遇到了一个偶数;

则拿一个奇数来和它换,odd++

②odd>n/2

且遇到了一个奇数

则拿一个偶数和它换,odd–

注意在换的时候,要保证,换过之后,序列中不会有相同的数字(即换完那一瞬间不能有相同的数字,也即换的那个数字不能和序列中的其他元素相同)



【Number Of WA】



2



【完整代码】

#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
#define Open() freopen("F:\\rush.txt","r",stdin)
#define Close() ios::sync_with_stdio(0),cin.tie(0)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5+100;
int n,m,a[N],odd=0,nodd,neven,flag,ans=0;
map <int,int> dic;
void swapeven(int i)
{
//    cout <<i<<endl;
while (neven<=m && dic[neven])
neven+=2;
if (neven>m)
flag = 0;
else
dic[a]--,dic[neven]=1,a = neven,neven+=2;
}
void swapodd(int i)
{
while (nodd<=m && dic[nodd])
nodd+=2;
if (nodd>m)
flag = 0;
else
dic[a]--,dic[nodd]=1,a = nodd,nodd+=2;
}
int main()
{
//Open();
Close();//scanf,puts,printf not use
//init??????
cin >> n >> m;
rep1(i,1,n)
{
cin >> a;
dic[a]++;
if (a&1) odd++;
}
nodd = 1,neven = 2;
flag = 1;
rep1(i,1,n)
{
if (dic[a]==1) continue;
ans++;
if (odd>n/2)
{
if (a%2==1)
odd--;
swapeven(i);
}
else
if (odd==n/2){
if (a%2==0)
swapeven(i);
else
//a%2==1
swapodd(i);
}
else{
//odd<n/2
if (a%2==0)
odd++;
swapodd(i);
}
}
rep1(i,1,n)
{
if (odd==n/2) break;
if (odd<n/2)
{
if (a%2==0)
{
odd++;
ans++;
swapodd(i);
}
}
else
{
//odd>n/2
if (a%2==1)
{
odd--;
ans++;
swapeven(i);
}
}
}
if (odd!=n/2 || !flag)
return cout<<-1<<endl,0;
cout << ans << endl;
rep1(i,1,n-1)
cout << a << ' ';
cout << a[n]<<endl;
return 0;
}