P7061 [NWRRC2014] Buffcraft 题解

scp020 · 2023-09-17 20:20:43 · 题解

P7061 [NWRRC2014] Buffcraft 题解

暴力题，建议评黄。

解法

注意到题中让 (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;
}