自动搬运

查看原文

来自洛谷，原作者为

	scp020 这是一个亖人 || 最后在线时间：2025年8月24日9时5分

搬运于2025-08-24 22:26:18，当前版本为作者最后更新于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;
}