【题目链接】: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[i]]--,dic[neven]=1,a[i] = neven,neven+=2;

}

void swapodd(int i)

{

    while (nodd<=m && dic[nodd])

        nodd+=2;

    if (nodd>m)

        flag = 0;

    else

        dic[a[i]]--,dic[nodd]=1,a[i] = nodd,nodd+=2;

}

int main()

{

    //Open();

    Close();//scanf,puts,printf not use

    //init??????

    cin >> n >> m;

    rep1(i,1,n)

    {

        cin >> a[i];

        dic[a[i]]++;

        if (a[i]&1) odd++;

    }

    nodd = 1,neven = 2;

    flag = 1;

    rep1(i,1,n)

    {

        if (dic[a[i]]==1) continue;

        ans++;

        if (odd>n/2)

        {

            if (a[i]%2==1)

                odd--;

            swapeven(i);

        }

        else

            if (odd==n/2){

                if (a[i]%2==0)

                    swapeven(i);

                else

                    //a[i]%2==1

                    swapodd(i);

            }

            else{

            //odd<n/2

                if (a[i]%2==0)

                    odd++;

                swapodd(i);

            }

    }

    rep1(i,1,n)

    {

        if (odd==n/2) break;

        if (odd<n/2)

        {

            if (a[i]%2==0)

            {

                odd++;

                ans++;

                swapodd(i);

            }

        }

        else

        {

            //odd>n/2

            if (a[i]%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[i] << ' ';

    cout << a[n]<<endl;

    return 0;

}