自动搬运

查看原文

来自洛谷，原作者为

	封禁用户 None

搬运于2025-08-24 22:46:34，当前版本为作者最后更新于2023-04-22 22:36:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

明明显显的贪心啊。注意叠词（

题目背景是一堆废话，没必要看。

为了使伤害最大，我们需要尽可能的使打出的攻击满足后两个规则。同时，我们还需要优先考虑大的 $a_i$。所以我们先将 $a$ 序列从大到小排序。在 $a_i$ 大的时候，我们需要拿 $b$ 序列来接应，注意的是，规则三中 $b_i$ 的值并不影响增加的值。

优先看规则二，我们从最大的 $a$ 进行枚举。若 $a_i × 2$ 的值大于对应 $b_i +k$ 的值，说明在这里运用规则三更好。由于规则一，同种元素不会抵消，我们完全可以以这个下标为割点，将后面的 $a_i$ 都先出，这样才能保证答案最大化。

为了更好理解，我们继续分析。题目要求将 $a$ 和 $b$ 全部打出去，所以答案的值至少是 $a,b$ 两序列的和。这样的话，在判断割点的时候，我们只需看 $a_i$ 是否小于 $k$ 就行了。

代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+100000;
bool cmp(int a,int b){return a>b;}
int n,m,k;
int a[N],b[N];
int ans,kk;
signed main() 
{
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++) cin>>a[i],ans+=a[i];
	for(int i=1;i<=m;i++) cin>>b[i],ans+=b[i];//求和
	sort(a+1,a+n+1,cmp);//贪心思路排序
	int minn=min(n,m);//这里一定是最小值
	for(int i=1;i<=minn;i++) if(a[i]>k) ans+=a[i],kk++;//规则二更优
	ans+=k*(minn-kk);//剩下的全部运用规则三
    return cout<<ans,0;
}

感谢 @seanlsy 大佬提出的改进方案。