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−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-deleted elements is zero.
Help Polycarp find this value.
Input
The first line of the input contains one integer n (1≤n≤2000) — the number of elements of a.
The second line of the input contains n integers a1,a2,…,an (0≤ai≤106), where ai is the i-th element of a.
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
题意：给定一个数组，进行操作每次删除一个数，但是删除的数的奇偶性必须要与上次删除的相反，求删除后剩下的数最小的和；
思路：输入的时候记录一下奇数和偶数的个数，首先如果奇数等于偶数，或者奇数和偶数个数相差为1个，那么可以全部删除，答案就是0，其余情况，遍历数组，奇数和偶数都删除奇偶个数之差个数，就ok了
参考代码：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define N 2005
#define ll long long int
using namespace std;
int a[N] ;
int main()
{
int n ;
cin >> n ;
int jj = 0 , oo = 0 ;
for(int i = 0 ; i < n ; i++)
{
cin>>a[i];
if(a[i] % 2 == 0 )
jj++ ;
else
oo++ ;
}
if(jj == oo || abs(jj - oo) == 1 )
{
cout << "0" << endl ;
return 0 ;
}
sort(a , a + n) ;
if( jj > oo )
{
ll ans = 0 ;
int l = jj - oo - 1 ;
for(int i = 0 ; i < n ; i++)
{
if( a[i] % 2 == 0 )
{
ans += a[i] ;
l-- ;
}
if(l == 0 )
break ;
}
cout << ans << endl ;
}
if(oo > jj )
{
ll ans = 0 ;
int l = oo - jj - 1 ;
for(int i = 0 ; i < n ; i++)
{
if( a[i] % 2 != 0 )
{
ans += a[i] ;
l-- ;
}
if(l == 0 )
break ;
}
cout << ans << endl ;
}
}
京公网安备 11010502036488号