Parity Alternated Deletions-CodeForces-1144B

2019.7.27

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.

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

我的思路：
用队列q来存储偶数，用队列p来存储奇数，且要求队列是从小到大排序。求出奇数个数和偶数个数的差值，来对队列里的数进行相应的删除操作，最后计算留在队列里的数的和即为所求。

#include <iostream>
#include <queue>
using namespace std;
priority_queue<int,vector<int>,less<int> > q;
priority_queue<int,vector<int>,less<int> > p;
int main()
{
    int n;
    long long a;
    cin >> n;
    int cha;
    long long ans = 0;
    for(int i=0; i<n; i++)
    {
        cin >> a;
        if(a%2 ==0)
            q.push(a);
        else
            p.push(a);
    }
    cha = q.size() - p.size();
    if(cha > 0)
    {
        while(!p.empty()){
            p.pop();
            q.pop();
        }
        q.pop();
        while(!q.empty())
        {
            ans += q.top();
            q.pop();
        }
    }
    else if(cha < 0)
    {
        while(!q.empty()){
            q.pop();
            p.pop();
        }
        p.pop();
        while(!p.empty())
        {
            ans += p.top();
            p.pop();
        }
    }
    else
        ans = 0;
    cout << ans << endl;
    return 0;
}