ZOJ4043 Virtual Singers

题目：

ZOJ4043 Virtual Singers

---

题解：

2018青岛热身赛的D题

注意反悔操作的处理，其他就贪心了

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int maxn = 100005;
struct V{
    ll x;
    int tag;
    V(){}
    V(ll _x, int _tag){
        x = _x;tag = _tag;
    }
    bool operator < (const V & _V) const{
        return x < _V.x;
    }
}a[maxn*2];
int m,n,t;
ll c,b,ans;
int main()
{
    scanf("%d",&t);
    while(t--)
    {
        priority_queue<ll, vector<ll>, greater<ll> > A,B,C;
        while(!A.empty())A.pop();
        while(!B.empty())B.pop();
        while(!C.empty())C.pop();

        int pos = 0;
        scanf("%d%d",&n,&m);
        for(int i = 0; i < n; i++){
            scanf("%lld", &c);
            a[pos++] = V(c,0);
        }
        for(int i = 0; i < m; i++){
            scanf("%lld", &b);
            a[pos++] = V(b, 1);
        }
        ans = 0;
        sort(a, a+m+n);
        for(int i = 0; i < m+n; i++)
        {
            if(a[i].tag == 0){
                if(!B.empty()){
                    ans += (a[i].x + B.top());
                    B.pop();
                }
                else if(!C.empty()){
                    if(a[i].x + C.top() < 0){
                        ans += (a[i].x + C.top());
                        A.push(-C.top()-a[i].x-a[i].x);
                        C.pop();
                    }
                    else{
                        A.push(-a[i].x);
                    }
                }
                else{
                    A.push(-a[i].x);
                }
            }
            else{
                if(!A.empty()){
                    ans += (a[i].x + A.top());
                    C.push(-A.top()-a[i].x-a[i].x);
                    A.pop();
                }
                else{
                    B.push(-a[i].x);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}