自动搬运

查看原文

来自洛谷，原作者为

	qkj_qwq 注意我的 Uid！|| 大号：qkj（Uid 1007676）|| 宣题目 U600000 || 宣比赛 240000 || 宣广告板 https://www.luogu.me/paste/aqn73hir

搬运于2025-08-24 21:17:48，当前版本为作者最后更新于2025-07-23 19:56:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路

贪心。

可以发现，在没有伤害翻倍的情况下，每个勇士的总攻击是不变的。这样，先把总攻击算出来（总攻击 $a_i=\left\lfloor\dfrac{H_i}{\text{ATK}}\right\rfloor\times A_i$），再从大到小排个序。

显然，要让总攻击最大的勇士乘的倍数最多。那么，如果要上 $i$ 个勇士，则 $i$ 个勇士的总攻击为 $a_i$ 的前缀和的前缀和（$a_i$ 的前缀和为 $a_1+a_2+\cdots+a_i$，$a_i$ 的前缀和的前缀和为 $a_1\times i+a_2\times(i-1)+\cdots+a_i\times1$）。从 $1$ 到 $n$ 遍历 $i$，若 $a_i$ 的前缀和的前缀和 $\ge\text{HP}$ 则输出 $i$，若无解输出 Fail。

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
int a[1000010];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int n,x,y;
	cin>>n>>x>>y;
	for(int i=1;i<=n;i++)
	{
		int xx,yy;
		cin>>xx>>yy;
		a[i]=yy/x*xx;
	}
	sort(a+1,a+n+1,greater<int>());
	for(int i=1;i<=n;i++)
		if(((a[i]+=a[i-1])+=a[i-1])>=y)
		{
			cout<<i;
			return 0;
		}
	cout<<"Fail";
	return 0;
}