题目描述
难度分:$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;
}
%%%