Artistic Balance Tree (CF R 1094 Div.1 + Div.2 - B)

https://codeforces.com/contest/2222/problem/B

---

아이디어

홀짝성이 같은 인덱스끼리는 뒤집기를 통해 마음대로 swap을 할 수 있습니다. 그러므로 마킹을 할 때에 최대한 큰것들을 마킹하기 위해서 마킹할 인덱스의 홀짝성을 바탕으로 홀수의 개수와 짝수의 개수를 세어주면 됩니다.

 

홀수 인덱스의 마킹 개수를 Odd라고 합시다. 그리고 홀수 인덱스의 수들을 OddNum이라고 합시다. 그러면 OddNum에서 가장 큰 Odd개를 마킹해주면 됩니다. 이때 이중에 음수가 끼어있으면 그 음수는 마킹하지 않습니다. 만약 모든 수가 음수라면 가장 큰 (절댓값이 가장 작은) 음수만을 마킹해주면 됩니다. 짝수도 마찬가지입니다.

---

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll T,N,M,i,x;

    cin>>T;
    while (T--)
    {
        cin>>N>>M;

        vector <ll> EvenNum,OddNum;
        ll sum=0;

        for (i=1;i<=N;i++)
        {
            cin>>x;
            sum+=x;
            if (i%2==0) EvenNum.push_back(x);
            else OddNum.push_back(x);
        }

        sort (EvenNum.begin(),EvenNum.end(),greater<>());
        sort (OddNum.begin(),OddNum.end(),greater<>());

        ll Even=0,Odd=0;
        for (i=1;i<=M;i++)
        {
            cin>>x;
            if (x%2==0) Even++;
            else Odd++;
        }

        for (i=0;i<min(Even,(ll)EvenNum.size());i++)
        {
            if (i!=0 && EvenNum[i]<0) break;
            sum-=EvenNum[i];
        }
        for (i=0;i<min(Odd,(ll)OddNum.size());i++)
        {
            if (i!=0 && OddNum[i]<0) break;
            sum-=OddNum[i];
        }

        cout<<sum<<"\n";
    }
}