[ABC062D] 3N Numbers

abensyl · 2023-02-03 15:43:42 · 题解

原题：ABC062D 3N Numbers。

非常好的一道题。

思路

本体我们可以把整个数列划分成两部分，取第一部分（前一段）前 n 大的值，第二部分（后一段）前 n 小的值。这样对两段分别加和，然后将两端的和作差即可。

很容易想到枚举分界线，对分界线两边的数字分别取最大值，时间复杂度 O(n^2\log n)，不可取。

枚举分界线的操作没有二分的性质，二分也不可取。

那么如果我们能够与处理好每个分界线所对应的前后两短的最大最小值，那么问题就迎刃而解了。

很显而易见，我们可以维护一个优先队列，最大值即为整个优先队列里前 n 大的值，维护最小值亦然，便于处理完成了。

代码整体时间复杂度：O(n \log n)。

注意：不开 long long 见祖宗！

代码

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 3e5 + 2;

int a[N], q[N], p[N];

signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n;
  cin >> n;
  priority_queue<int, vector<int>, greater<int>> pq;
  int sum = 0;
  for (int i = 1; i <= 3 * n; ++i) {
    cin >> a[i];
    pq.push(a[i]), sum += a[i];
    while (pq.size() > n) sum -= pq.top(), pq.pop();
    q[i] = sum;
  }
  priority_queue<int> qp;
  sum = 0;
  for (int i = 3 * n; i >= 1; --i) {
    qp.push(a[i]), sum += a[i];
    while (qp.size() > n) sum -= qp.top(), qp.pop();
    p[i] = sum;
  }
  int res = -1e18;
  for (int i = n; i <= n * 2; ++i) res = max(res, q[i] - p[i + 1]);
  cout << res << '\n';
  return 0;
}