暴力题,建议评黄。
解法
注意到题中让 $(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;
}