题意
给定一个长度为 \(N\) 的正整数数列 \(A\)，和一个长度为 \(M\) 的正整数数列 \(B\)，还有一个正整数 \(P\)。
你需要求：
\[\sum\limits^{N}_{i=1}\sum\limits^{M}_{j=1}\min(A_i+B_j,P) \]分析
说实话感觉这题比 C 还要简单。
先考虑单个 \(A_i\) 能产生的贡献，可以发现当 \(B_j \ge P - A_i\) 时产生的贡献只有 \(P\)。
所以先将 \(B\) 数组排序，二分找到第一个 \(B_x \ge P - A_i\) 的地方。所以这一部分的所有的答案贡献即为 \((M-x+1)P\)。
再考虑 \(B_j < P - A_i\) 的这部分情况，很容易发现这一部分的答案就是 \(A_i(x-1)+\sum\limits^{x-1}_{i=1}B_i\)，可以发现一个前缀和的结构，提前预处理就好了。
时间复杂度 \(O(n \log m + m \log m)\)。
代码
//the code is from chenjh
#include<cstdio>
#include<algorithm>
#define MAXN 200002
using namespace std;
typedef long long LL;
int n,m,p;
int a[MAXN],b[MAXN];
LL s[MAXN];//b 的前缀和。
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(b+1,b+m+1);//排序。
for(int i=1;i<=m;i++) s[i]=s[i-1]+b[i];
LL ans=0;
for(int i=1,x;i<=n;i++){
x=lower_bound(b+1,b+m+1,p-a[i])-b;//找到第一个 b[x]>=p-a[i] 的位置。
ans+=(LL)a[i]*(x-1)+s[x-1]+(LL)p*(m-x+1);//两部分的贡献加起来即可。
}
printf("%lld\n",ans);
return 0;
}