DDOSvoid's Blog

校内赛 合并数组

发表于 更新于 分类于
本文字数： 1.3k 阅读时长 ≈ 1 分钟

题目描述

简要题意：给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，令 $s_i$ 表示 $b$ 中前 $i$ 大的数字之和，要求 $c_i=\max(a_j+s_{i-j}),j<i$

$n\le 10^5$

Solution

我们不妨将求 $c_i$ 的过程看成一个 $dp$，同时用 $f_i$ 代替 $c_i$

然后我们发现 $f$ 的决策点是具有单调性的，因为 $s$ 的增量是越来越小的

然后我们选择单调队列二分还是直接分治都行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <algorithm>
#define maxn 100010
#define ll long long
using namespace std;

int n;

ll a[maxn], b[maxn];

inline ll F(int x, int y) { return a[x] + b[y - x]; } 

struct Queue {
    int l, r, k;
} Q[maxn]; int h, t;

int bs(int x) {
    int l = Q[t].l, r = Q[t].r, mid, ans = Q[t].r + 1;
    while (l <= r) {
        mid = l + r >> 1;
        if (F(x, mid) >= F(Q[t].k, mid)) ans = mid, r = mid - 1;
        else l = mid + 1; 
    } return ans;
}

ll f[maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n;
    for (int i = 0; i <= n; ++i) cin >> a[i];
    for (int i = 1; i <= n; ++i) cin >> b[i];
    sort(b + 1, b + n + 1, greater<ll>());
    for (int i = 1; i <= n; ++i) b[i] += b[i - 1];
    Q[h = t = 1] = { 1, n, 0 };
    for (int i = 1; i <= n; ++i) {
        while (h < t && Q[h].r < i) ++h;
        f[i] = F(Q[h].k, i);
        while (h < t && i < Q[t].l && F(i, Q[t].l) >= F(Q[t].k, Q[t].l)) --t;
        int p = bs(i); Q[t].r = p - 1;
        if (p <= n) Q[++t] = { p, n, i };
    }
    for (int i = 1; i <= n; ++i) cout << f[i] << " ";
    return 0;
}