【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 = {0,1,-1,0,0,-1,-1,1,1};
const int dy = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 2e5+100;
int n,m,a,odd=0,nodd,neven,flag,ans=0;
map <int,int> dic;
void swapeven(int i)
{
// cout <<i<<endl;
while (neven<=m && dic)
neven+=2;
if (neven>m)
flag = 0;
else
dic]--,dic=1,a = neven,neven+=2;
}
void swapodd(int i)
{
while (nodd<=m && dic)
nodd+=2;
if (nodd>m)
flag = 0;
else
dic]--,dic=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]++;
if (a&1) odd++;
}
nodd = 1,neven = 2;
flag = 1;
rep1(i,1,n)
{
if (dic]==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<<endl;
return 0;
}
页:
[1]