萌新初做黑题,求助!
查看原帖
萌新初做黑题,求助!
366937
too_simple楼主2022/7/25 11:25
#include <iostream>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

inline int read() {
    char c = getchar();
    int s = 1, x = 0;
    while(c < '0' || c > '9') {
        if(c == '-') s = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return s * x;
}

const int N = 1e6 + 6;
const int INF = 1e9 + 7;

int T, n, k, l;
int a[N], b[N], res[N];
long long ans;

struct Node {
    int val, i;
    bool operator >(const Node & jq) const {
        return val > jq.val;
    }
};

struct student {
    int a, b, i;
}st[N];

priority_queue<Node, vector<Node>, greater<Node>> q1, q2, q3, q4, q5, q6;//q1存a[i],q2存-a[i],q3存b[i],q4存-b[i],q5存a[i]+b[i],q6存-(a[i]+b[i])

void init() {
    ans = 0;
    while ( q1.size()) q1.pop();
    while ( q2.size()) q2.pop();
    while ( q3.size()) q3.pop();
    while ( q4.size()) q4.pop();
    while ( q5.size()) q5.pop();
    while ( q6.size()) q6.pop();
}

bool Cmp1(student x, student y) {
    return x.a != y.a ? x.a > y.a : x.b > y.b;
}

bool Cmp2(student x, student y) {
    return x.b != y.b ? x.b > y.b : x.a > y.a;
}

int main() {
    
    scanf("%d", &T);
    
    while( T -- ) {
        n = read(), k = read(), l = read();
        init();
        for(int i = 1; i <= n; ++ i) {
            st[i].a = read();
            st[i].i = i;
        }
        for(int i = 1; i <= n; ++ i) {
            st[i].b = read();
        }
        sort(st + 1, st + 1 + n, Cmp1);
        for(int i = 1; i <= k; i ++) {
            ans += st[i].a;
            res[st[i].i] += 1;
        }
        sort(st + 1, st + 1 + n, Cmp2);
        for(int i = 1; i <= k; ++ i) {
            ans += st[i].b;
            res[st[i].i] += 2;
        }
        for(int i = 1; i <= n; ++ i) {
            if(res[st[i].i] == 3) {
                l --;
                q6.push({-(st[i].b + st[i].b), st[i].i});
            }
            else if(res[st[i].i] == 2) {
                q1.push({st[st[i].i].a, st[i].i});
                q4.push({-st[st[i].i].b, st[i].i});
            }
            else if(res[st[i].i] == 1) {
                q3.push({st[st[i].i].b, st[i].i});
                q2.push({-st[st[i].i].a, st[i].i});
            }
            else q5.push({st[i].a + st[i].b, st[i].i});
        }
        l = max(l, 0);
        while( l -- ) {
            while(q1.size() && res[q1.top().i] != 2) q1.pop();
            while(q2.size() && res[q2.top().i] != 1) q2.pop();
            while(q3.size() && res[q3.top().i] != 1) q3.pop();
            while(q4.size() && res[q4.top().i] != 2) q4.pop();
            while(q5.size() && res[q5.top().i]) q5.pop();
            while(q6.size() && res[q6.top().i] != 3) q6.pop();
            int c1 = INF, c2 = INF, c3 = INF, c4 = INF;
            if(q1.size() && q2.size()) c1 = q1.top().val + q2.top().val;
            if(q3.size() && q4.size()) c2 = q3.top().val + q4.top().val;
            if(q2.size() && q4.size() && q5.size()) c3 = q2.top().val + q4.top().val + q5.top().val;
            if(q1.size() && q3.size() && q6.size()) c4 = q1.top().val + q3.top().val + q6.top().val;
            int op = max(max(c1, c2), max(c3, c4));
            if(c1 == op) {
                ans += c1;
                res[q1.top().i] = 3, res[q2.top().i] = 0;
                q6.push({-(st[q1.top().i].a + st[q1.top().i].b), q1.top().i});
                q5.push({st[q2.top().i].a + st[q1.top().i].b, q2.top().i});
                q1.pop(), q2.pop();
            }
            else if(c2 == op) {
                ans += c2;
                res[q3.top().i] = 3, res[q4.top().i] = 0;
                q6.push({-(st[q3.top().i].a + st[q3.top().i].b), q3.top().i});
                q5.push({st[q4.top().i].a + st[q4.top().i].a, q4.top().i});
                q3.pop(), q4.pop();
            }
            else if(c3 == op) {
                ans += c3;
                res[q5.top().i] = 3, res[q2.top().i] = 0, res[q4.top().i] = 0;
                q6.push({-q5.top().val, q5.top().i});
                q1.push({-q2.top().val, q2.top().i});
                q3.push({-q4.top().val, q4.top().i});
                q2.pop(), q4.pop(), q5.pop();
            }
            else {
                ans += c4;
                res[q6.top().i] = 0, res[q1.top().i] = 3, res[q3.top().i] = 3;
                q5.push({-q6.top().val, q6.top().i});
                q6.pop();
                q6.push({-(st[q1.top().i].a + st[q1.top().i].b), q1.top().i});
                q6.push({-(st[q3.top().i].a + st[q3.top().i].b), q3.top().i});
                q1.pop(), q3.pop();
            }
        }
    }
    
    printf("%lld", ans);
    
    return 0;
}
2022/7/25 11:25
加载中...