广州XP03B集训比赛的第十题
2026-08-03 19:22:43
发布于：广东
广州集训今天比赛的第十题，AK哥做出来了@假伪人
T116587.奶茶搭配
普及/提高-
加入题单
通过率：
53.33%
时间限制：
1.00s
内存限制：
128MB
题目描述
小码奶茶店新开业！有 N 种茶底和 M 种小料。
一杯奶茶 = 1 种茶底 + 1 种小料，价格就是茶底价加小料价。
但小码王搞了个封顶价 P 元——如果茶底加小料的价格超过 P 元，就只收 P 元！
小码君帮忙算算：所有 N×M 种搭配，一共能卖出多少钱？
输入格式
第一行三个整数 N,M,P，分别表示茶底种类数、小料种类数和封顶价格。（1≤N,M≤2×10
5
，1≤P≤2×10
8
）
第二行 N 个整数 A
i
，表示每种茶底的价格。（1≤A
i
≤10
8
）
第三行 M 个整数 B
j
，表示每种小料的价格。（1≤B
j
≤10
8
）
输出格式
输出一个整数，表示所有奶茶搭配的总收入。答案在 64 位有符号整数范围内。
输入输出样例
输入#1
2 2 6
2 4
3 5
输出#1
23
输入#2
2 2 100
1 2
3 4
输出#2
20
输入#3
2 2 5
4 5
6 7
输出#3
20
输入#4
7 12 25514963
2436426 24979445 61648772 23690081 33933447 76190629 62703497
11047202 71407775 28894325 31963982 22804784 50968417 30302156 82631932 61735902 80895728 23078537 7723857
输出#4
2115597124
说明/提示
【样例 1 解释】
茶底 [2,4]，小料 [3,5]，封顶价 6 元。有部分搭配超过封顶价：
茶底 小料 原价 实付
2 3 5 5
2 5 7 6（封顶）
4 3 7 6（封顶）
4 5 9 6（封顶）
总收入 =5+6+6+6=23 元。
【样例 2 解释】
茶底 [1,2]，小料 [3,4]，封顶价 100 元。所有原价都不超过 100，没有触发封顶：
茶底 小料 原价 实付
1 3 4 4
1 4 5 5
2 3 5 5
2 4 6 6
总收入 =4+5+5+6=20 元。
【样例 3 解释】
茶底 [4,5]，小料 [6,7]，封顶价 5 元。所有原价都超过 5，全部按封顶价 5 元收：
茶底 小料 原价 实付
4 6 10 5（封顶）
4 7 11 5（封顶）
5 6 11 5（封顶）
5 7 12 5（封顶）
总收入 =5×4=20 元。
【样例 4 解释】
7 种茶底、12 种小料，封顶价 25514963 元。共有 7×12=84 种搭配，部分原价超过封顶价，部分没有。把每种搭配的实付加起来，总收入为 2115597124 元。
#include<iostream>
#include<algorithm>
using namespace std;
long long a[200001],b[200001],n,m,p,sum1,sum2,ans;
int main(){
cin>>n>>m>>p;
for(int i=1;i<=n;i++) cin>>a[i];
for(int i=1;i<=m;i++){
cin>>b[i];
sum1+=b[i];//sum1=b数组总和
}
sort(a+1,a+1+n);
sort(b+1,b+1+m);//升序排序
for(int i=1,j=m;i<=n&&j!=0;){//双指针
if(a[i]+b[j]<=p){
ans+=sum1+a[i]*j;
sum2+=j;
i++;
}
else {
sum1-=b[j];//sum1模拟前缀和
j--;
}
}
cout<<ans+(n*m-sum2)*p;//n*m是总方法数,sum2是去掉<=p的方法数,ans是<=p的方法总和
return 0;
}
有帮助，赞一个