题解：AT_arc074_b [ABC062D] 3N Numbers

ruik · 2025-01-09 13:02:03 · 题解

题意

给你一个大小为 3 \times n 数组，要你找到一位置 i(1 \le i \le 3 \times n) 将它分为两个数组，并在两个数组中分别选取 n 个数并分别求和，使得两数组和的差最大。

思路

由于最后求和的两个数组不能有重合部分，所以我们只需要对所有的 i(n \le i \le 2 \times n) 进行枚举，取最大的值即可为什么为 (n \le i \le 2 \times n)？因为两个数组都必须至少有 n 个数。

那对于一个 i，如何求出它两边数组差的最大值呢？这我们就需要用到优先队列了。优先队列总的说就是一种可以对集合中的数求最小或最大的工具，具体用法可以自行查阅。总之，我们先将 n 个数放入优先队列，然后在便利的同时将优先队列中更小的数去除，加入更大的数来维持优先队列中存的是集合中的最大的 n 个数。

code

#include<bits/stdc++.h>
using namespace std;
long long n,a[300200],f[300200],sum[300200],m=-1e18;
priority_queue<long long>q; 
priority_queue<long long>p; 
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=3*n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=n;i++){
        q.push(-a[i]);
        f[i]=f[i-1]+a[i];
    }
    for(int i=n+1;i<=2*n;i++){
        f[i]=f[i-1];
        if(a[i]>-q.top()){
            f[i]=f[i-1]+q.top()+a[i];
            q.pop();
            q.push(-a[i]);
        }
    }
    for(int i=3*n;i>2*n;i--){
        sum[2*n+1]+=a[i];
        p.push(a[i]);
    }
    for(int i=2*n;i>=n;i--){
        if(a[i]<p.top()){
            sum[i]=sum[i+1]-p.top()+a[i];
            p.pop();
            p.push(a[i]);
        }
        else sum[i]=sum[i+1];
        m=max(m,f[i]-sum[i+1]);
    }
    cout<<m;
    return 0;
}