AT_abc396_c [ABC396C] Buy Balls 题解

考察知识

1. 贪心
2. 分类讨论

题目大意

有 $N$ 个黑球和 $M$ 个白球，每个球都有一个值。在黑球的数量大于等于白球的数量的前提下，使所选球的数值和最大。
注意：数值可能为负数。

思路

考虑贪心。

显然，黑球的所有正数我们都会选，设所选黑球数量为 $n$，白球剩余的正数数量为 $m$，之后会出现两种情况：

• 当 $n \ge m$ 时：显然，应该把这 $m$ 个球都选了，此时即为最优。因为剩余数全为负数，再次选择必然会使总和变小。
• 当 $n < m$ 时：先将最大的 $n$ 个白球计入总和。之后我们先考虑数值最大的白球，设为 $x$，设此时未选择的数值最大的黑球为 $y$，那么如果此时 $x + y > 0$，则加入总和（因为可以增加总和），否则此时总和即为答案。之后按以上方式一直计算其他球。

实现

我们可以先对两个数组进行排序，之后按照思路部分模拟即可。

代码参考

// Problem: C - Buy Balls
// Contest: AtCoder - AtCoder Beginner Contest 396
// URL: https://atcoder.jp/contests/abc396/tasks/abc396_c
// Memory Limit: 1024 MB
// Time Limit: 2000 ms#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N=2e5+10;
int n,m;
int a[N],b[N];
ll ans;
bool cmp(int a,int b){return a>b;
}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;++i) scanf("%d",&a[i]);for(int i=1;i<=m;++i) scanf("%d",&b[i]);sort(a+1,a+n+1,cmp);sort(b+1,b+m+1,cmp);int cnt = 1;       //cnt表示当前的白球for(int i=1;i<=n;++i){if(a[i] >= 0){ans += a[i];if(b[cnt] >= 0) ans += b[cnt++];}else {if(a[i] + b[cnt] >= 0) ans += a[i] + b[cnt++];else break;}//printf("%lld %d\n",ans,cnt);}printf("%lld",ans);return 0;
}