P7061 [NWRRC2014] Buffcraft 题解

2023/09/17 Blog

暴力题,建议评黄。

解法

注意到题中让 $(b + d_1 + d_2 + \cdots + d_n)(100 + p_1 + p_2 + \cdots + p_m) \div 100$ 尽量大,又因为所以的 $d_i , p_i$ 非负,所以尽可能的去 $d , p$ 中较大值,总和不超过 $k$ 即可,可以用排序解决。

枚举每种可能的 $n , m$ 的取值,这可能用到前缀和,计算 $(b + pred_n) \times (100 + prep_m) \div 100$,取最大值更新答案。当然,因为我们的枚举过程中 $n$ 为单调不减,$m$ 为单调不增,所以可以不用前缀和。

总复杂度 $\mathcal{O}(n \log n)$。

代码

#include<bits/stdc++.h>
using namespace std;
namespace fast_IO
{
    /*
    快读快写。
    */
};
using namespace fast_IO;
// 警告:本题没有提供 n 和 m(即 cd 和 cp)的范围,所以要开大一点,我在这里栽了好几次
int B,k,n,m,ans1,ans2;
long long buff1[500010],buff2[500010];
// buff 是前缀和预处理,可以一定程度上的加速(当然,可以利用 i 和 j 的单调性来加速,但是显然比前缀和麻烦)
long double ans,now;
struct num
{
    int x,index;
    inline bool operator<(const num &y) const
    {
        return x>y.x;
    }
};
num d[500010],p[500010];
int main()
{
    read(B),read(k),read(n),read(m);
    for(int i=1;i<=n;i++) read(d[i].x),d[i].index=i;
    for(int i=1;i<=m;i++) read(p[i].x),p[i].index=i;
    sort(d+1,d+n+1),sort(p+1,p+m+1);
    for(int i=1;i<=n;i++) buff1[i]=buff1[i-1]+d[i].x;
    for(int i=1;i<=m;i++) buff2[i]=buff2[i-1]+p[i].x;
    // 先枚举 d 中的 buff,i 代表要在 d 中取几个,j 代表要在 p 中取几个,注意严格控制 i 和 j 的范围,别取多了
    for(int i=0,j;i<=n && i<=k;i++)
    {
        j=min(k-i,m),now=((B+buff1[i])*(100+buff2[j])/100.0);
        if(now>ans) ans=now,ans1=i,ans2=j;
    }
    write(ans1),Putchar(' '),write(ans2),Putchar('\n');
    for(int i=1;i<=ans1;i++) write(d[i].index),Putchar(' ');
    Putchar('\n');
    for(int i=1;i<=ans2;i++) write(p[i].index),Putchar(' ');
    fwrite(Ouf,1,p3-Ouf,stdout),fflush(stdout);
    return 0;
}
对我博客最大的鼓励来自于你的评论(什么玩梗),欢迎选择 来回复, 也可以在 GitHub discussion 留言。

Search

    公告

    博主这下真摆烂了。我下辈子也不碰 Jekyll 和 MathJax 了!
    留言板,现在博主的精神状态非常好,有事烧纸。

    联系方式

    QQ: 33299235
    email: 33299235@qq.com
    Gmail: scp020.cn@gmail.com

    本人的其它个人主页

    洛谷
    CSDN

    友链

    拜谢stevehim(已退役,祝好)
    拜谢日记
    拜谢cppomstar

    views counting

    Document

    Table of Contents