题目描述

难度分:$806$

输入$n$，$m(1 \leq n,m \leq 2 \times 10^5)$，$p(1 \leq p \leq 2 \times 10^8)$，和长度分别为$n$和$m$的数组$a$和$b$，元素范围是$[1,10^8]$。

输出如下程序打印的值：

sum = 0
for x in a:
    for y in b:
        sum += min(x + y, p)
print(sum)

输入样例$1$

2 2 7
3 5
6 1

输出样例$1$

24

输入样例$2$

1 3 2
1
1 1 1

输出样例$2$

6

输入样例$3$

7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857

输出样例$3$

2115597124

算法

前缀和+二分

先将$a$和$b$两个数组排序，并求出对应的前缀和数组$sa$和$sb$。接下来枚举$a[i]$（$i \in [1,n]$），二分找到最后一个满足$a[i]+b[j] \leq p$的$b[j]$，那么$a[i]$对答案的贡献就应该是$a[i] \times j + \Sigma_{k=1}^{j}b[k] + p \times (m - j)$。

遍历所有的$a[i]$，把它们对应的贡献都累加起来就是答案。

复杂度分析

时间复杂度

对两个数组排序，时间复杂度为$O(nlog_2n+mlog_2m)$，求前缀和数组时间复杂度为$O(n+m)$；接下来枚举$a[i]$，二分找到临界的$b[j]$并计算答案，时间复杂度为$O(nlog_2m)$。如果将$n$和$m$看成是同一规模$N$，则算法整体的时间复杂度为$O(Nlog_2N)$。

空间复杂度

算法主要的空间消耗瓶颈在于两个前缀和数组$sa$和$sb$，额外空间复杂度为$O(n+m)$。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 200010;
int n, m, p;
int a[N], b[N];
LL sa[N], sb[N];

int main() {
    scanf("%d%d%d", &n, &m, &p);
    for(int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    for(int i = 1; i <= m; i++) {
        scanf("%d", &b[i]);
    }
    sort(a + 1, a + n + 1);
    sort(b + 1, b + m + 1);
    for(int i = 1; i <= n; i++) {
        sa[i] = sa[i - 1] + a[i];
    }
    for(int i = 1; i <= m; i++) {
        sb[i] = sb[i - 1] + b[i];
    }
    LL ans = 0;
    for(int i = 1; i <= n; i++) {
        int j = upper_bound(b + 1, b + m + 1, p - a[i]) - b;
        --j;
        ans += (LL)a[i]*j + sb[j] + (LL)p*(m - j);
    }
    printf("%lld\n", ans);
    return 0;
}