Numbers Exchange
题意：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, 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);
if(a % 2 == 0) cnt0++;
else cnt1++;
mp.insert(a);
}
// cout << cnt0 << ' ' << cnt1 << endl;
for(int i = 1;i <= n;i++)
{
if(Tp.count(a))
{
if(a&1) cnt1--;
else cnt0--;
int tmp0 = get(0), tmp1 = get(1);
if(cnt0 < cnt1 && tmp0) a = tmp0;
else if(cnt1 < cnt0 && tmp1) a = tmp1;
else if(tmp0) a = tmp0;
else if(tmp1) a = tmp1;
else
{
puts("-1");
return 0;
}
ans++;
mp.insert(a);
if(a&1) cnt1++;
else cnt0++;
}
Tp.insert(a);
}
// cout << "ans = " << ans << endl;
// for(int i = 1;i <= n;i++) cout << a << ' ';
// cout << endl << cnt0 << ' ' << cnt1 << endl;
for(int i = 1;i <= n && cnt0 != cnt1;i++)
{
if(cnt0 < cnt1 && a % 2 == 1)
{
cnt0++;
cnt1--;
int tmp = get(0);
if(tmp) a = tmp, ans++;
else
{
puts("-1");
return 0;
}
}
if(cnt1 < cnt0 && a % 2 == 0)
{
cnt0--;
cnt1++;
int tmp = get(1);
if(tmp) a = tmp, ans++;
else
{
puts("-1");
return 0;
}
}
mp.insert(a);
}
cout << ans << endl;
for(int i = 1;i <= n;i++) cout << a << ' ';
cout << endl;
return 0;
}
View Code
页:
[1]