Polycarp has an array aa consisting of nn integers.
He wants to play a game with this array. The game consists of several moves. On the first move he chooses any element and deletes it (after the first move the array contains n−1n−1 elements). For each of the next moves he chooses any element with the only restriction: its parity should differ from the parity of the element deleted on the previous move. In other words, he alternates parities (even-odd-even-odd-... or odd-even-odd-even-...) of the removed elements. Polycarp stops if he can't make a move.
Formally:
If it is the first move, he chooses any element and deletes it;
If it is the second or any next move:
if the last deleted element was odd, Polycarp chooses any even element and deletes it;
if the last deleted element was even, Polycarp chooses any odd element and deletes it.
If after some move Polycarp cannot make a move, the game ends.
Polycarp's goal is to minimize the sum of non-deleted elements of the array after end of the game. If Polycarp can delete the whole array, then the sum of non-deletedelements is zero.
Help Polycarp find this value.
Input
The first line of the input contains one integer nn (1≤n≤20001≤n≤2000) — the number of elements of aa.
The second line of the input contains nn integers a1,a2,…,ana1,a2,…,an (0≤ai≤1060≤ai≤106), where aiaiis the ii-th element of aa.
Output
Print one integer — the minimum possible sum of non-deleted elements of the array after end of the game.
Examples
Input
5
1 5 7 8 2
Output
0
Input
6
5 1 2 4 6 3
Output
0
Input
2
1000000 1000000
Output
1000000
Codeforces Round #550 (Div. 3)B. Parity Alternated Deletions - nuoyanli的博客 - CSDN博客
B. Parity Alternated Deletions - weixin_44417851的博客 - CSDN博
题意：给定一个数组，进行操作每次删除一个数，但是删除的数的奇偶性必须要与上次删除的相反，求删除后剩下的数最小的和； 思路：输入的时候记录一下奇数和偶数的个数，首先如果奇数等于偶数，或者奇数和偶数个数相差为1个，那么可以全部删除，答案就是0，其余情况，遍历数组，奇数和偶数都删除奇偶个数之差个数，就ok了 --------------------- 作者：nuoyanli 来源：CSDN 原文：https://blog.csdn.net/nuoyanli/article/details/88942205 版权声明：本文为博主原创文章，转载请附上博文链接！
计量偶数与奇数分别有多少个，并且单独储存，当奇数偶数数量相同时，输出0，不相等让把多的那个的数加到sum里（加数量差并减去第一次任意删除的那一个）
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<vector>
#include<set>
#include<iostream>
#include<algorithm>
#define N 2005
#define ll long long
using namespace std;
int main() {
int n;
int a[N];
cin>>n;
int t=0,s=0;
for(int i=0;i<n;i++){
cin>>a[i];
if(a[i]%2==0)
t++;
else s++;
}
if(t==s||(abs(t-s)==1)){
cout<<"0"<<endl;
return 0;
}
sort(a,a+n);
if(t>s){
ll sum=0;
int l=t-s-1;
for(int i=0;i<n;i++){
if(a[i]%2==0){
sum+=a[i];
l--;
}
if(l==0)break;
}
cout<<sum<<endl;
}
if(s>t){
ll sum=0;
int l=s-t-1;
for(int i=0;i<n;i++){
if(a[i]%2!=0){
sum+=a[i];
l--;
}
if(l==0)
break;
}
cout<<sum<<endl;
}
}
网友评论