题目链接
Polycarp has an array a consisting of n 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?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.
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
题意:
给你一串数字，一开始任意删除一个数字，接下来的每一次操作如果上一个数字是奇数，那么这次删除偶数，如果上次是偶数，这次删除奇数，循环往复，直到奇数或者偶数至少有一个没有，计算剩下的最小和
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N = 2050;
int n,t,oi,ei,sum,odd[N],even[N];
bool cmp(int a,int b){
return a > b;
}
int main(){
cin >> n;for(int i = oi = ei = 0;i < n;i++){
cin >> t;if(t & 1){
//统计奇数和偶数个数odd[oi++] = t;}else{
even[ei++] = t;}}sort(odd,odd + oi,cmp);//排序 因为要最小和sort(even,even + ei,cmp);if(oi > ei + 1){
sum = 0;for(int i = ei + 1;i < oi;i++){
sum += odd[i];}}else if(oi == ei + 1){
sum = 0;}else{
for(int i = oi + 1;i < ei;i++){
sum += even[i];}}cout << sum << endl;return 0;
}