P9228 原神 题解

cq_zry · 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 大佬提出的改进方案。