题解 [ABC321D] Set Menu

cjh20090318 · 2023-09-24 15:08:12 · 题解

题意

给定一个长度为 N 的正整数数列 A，和一个长度为 M 的正整数数列 B，还有一个正整数 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;
}