首页 > 代码库 > Numbers Exchange

Numbers Exchange

2024-09-18 01:50:44   220人阅读

题意：

Eugeny有n张卡片，他希望和Nikolay交换一些卡片使得他拥有的奇数数字和偶数数字的卡片数目一样，且所有数字都不同。

Nikolay有m张卡片，分别写着1到m。问最少交换几次，能够满足要求。并输出交换后的结果。无解输出-1，多解任意输出一组。

 

解法：

贪心，首先用没有出现过的数字填好重复出现的数字，并顺便尽量让odd，even差值较小。

然后贪心用没出现的数字填即可。

 

技术分享 
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

#define N 200010

using namespace std;

int n, m, a[N], j = 2, k = 1;
set<int> mp, Tp;

int get(int x)
{
    if(x == 0)
    {
        while(j <= m && mp.count(j)) j += 2;
        if(j <= m) return j;
        else return 0;
    }
    else
    {
        while(k <= m && mp.count(k)) k += 2;
        if(k <= m) return k;
        else return 0;
    }
}

int main()
{
    scanf("%d %d", &n, &m);
    int cnt0 = 0, cnt1 = 0, ans = 0;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d", &a[i]);
        if(a[i] % 2 == 0) cnt0++;
        else cnt1++;
        mp.insert(a[i]);
    }
//    cout << cnt0 << ‘ ‘ << cnt1 << endl;
    for(int i = 1;i <= n;i++)
    {
        if(Tp.count(a[i]))
        {
            if(a[i]&1) cnt1--;
            else cnt0--;
            int tmp0 = get(0), tmp1 = get(1);
            if(cnt0 < cnt1 && tmp0) a[i] = tmp0;
            else if(cnt1 < cnt0 && tmp1) a[i] = tmp1;
            else if(tmp0) a[i] = tmp0;
            else if(tmp1) a[i] = tmp1;
            else
            {
                puts("-1");
                return 0;
            }
            ans++;
            mp.insert(a[i]);
            if(a[i]&1) cnt1++;
            else cnt0++;
        }
        Tp.insert(a[i]);
    }
//    cout << "ans = " << ans << endl;
//    for(int i = 1;i <= n;i++) cout << a[i] << ‘ ‘;
//    cout << endl << cnt0 << ‘ ‘ << cnt1 << endl;
    for(int i = 1;i <= n && cnt0 != cnt1;i++)
    {
        if(cnt0 < cnt1 && a[i] % 2 == 1)
        {
            cnt0++;
            cnt1--;
            int tmp = get(0);
            if(tmp) a[i] = tmp, ans++;
            else
            {
                puts("-1");
                return 0;
            }
        }
        if(cnt1 < cnt0 && a[i] % 2 == 0)
        {
            cnt0--;
            cnt1++;
            int tmp = get(1);
            if(tmp) a[i] = tmp, ans++;
            else
            {
                puts("-1");
                return 0;
            }
        }
        mp.insert(a[i]);
    }
    cout << ans << endl;
    for(int i = 1;i <= n;i++) cout << a[i] << ‘ ‘;
    cout << endl;
    return 0;
}
View Code

 

Numbers Exchange


联系
我们