题解：AT_abc396_c [ABC396C] Buy Balls

题面

题目描述

有

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

CPP

#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;
}

题解：AT_abc396_c [ABC396C] Buy Balls

文章操作

题面

题目描述

数据范围

解题思路

Code

相关推荐

评论

题解：AT_abc396_c [ABC396C] Buy Balls