题解：AT_abc396_c [ABC396C] Buy Balls

ZZ0520 · 2025-03-08 22:36:47 · 题解

题面

题目描述

有 N 黑球和 M 白球。

每个球都有一个值。第 i 个黑球（ 1 \le i \le N ）的值为 B_i，第 j 个白球（ 1 \le j \le M ）的值为 W_j。

选择 0 个或多个球，使选中的黑球的数量至少等于选中的白球的数量。在所有这些选择中，找出所选球值的最大可能和。

数据范围

• 1 \leq N,M \leq 2\times 10^5
• -10^9 \leq B_i, W_j \leq 10^9

解题思路

• 排序和前缀和计算：首先将黑球和白球按值降序排列，并计算它们的前缀和数组。前缀和数组帮助我们快速找到前 k 个最大值的总和。

• 预处理最大值数组：对于每个可能的 k（黑球数量），预处理一个数组，使得该数组中的每个元素表示从 k 到 n 的最大前缀和。这样我们可以快速得到在至少选择k个黑球时的最大总价值。

• 遍历所有可能的白球数量：对于每个可能的白球数量 k，计算对应的最大总价值，即白球前 k 个值的总和加上至少 k 个黑球的最大总和。遍历所有可能的 k 值，找到最大值。

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
    int n,m;
    cin>>n>>m;
    vector<ll> b(n,0),w(m,0);
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    for(int j=0;j<m;j++){
        cin>>w[j];
    }
    sort(b.begin(),b.end(),greater<ll>());//黑球按值降序排列
    sort(w.begin(),w.end(),greater<ll>());//白球按值降序排列
    vector<ll> bs(n+5,0);
    for(int i=1;i<=n;i++){
        bs[i]=bs[i-1]+b[i-1];//计算黑球的前缀和数组
    }
    vector<ll> ws(m+5,0);
    for(int j=1;j<=m;j++){
        ws[j]=ws[j-1]+w[j-1];//计算白球的前缀和数组
    }
    vector<ll> mx(n+5,0);
    mx[n]=bs[n];
    for(int i=n-1;i>=0;i--){
        mx[i]=max(bs[i],mx[i+1]);//预处理
    }
    int k=min(m,n);
    ll ans=0;
    for(int i=0;i<=k;i++){//遍历所有可能的白球数量
        ll cnt=ws[i]+mx[i];
        if(cnt>ans){
            ans=cnt;
        }
    }
    cout<<ans;
    return 0;
}