E.游戏人生

贪心。考虑从第 $11$ 回合到第 $nn$ 回合依次构造最优状态。

首先定义 BOSS 的生命值 $hphp$ 为击败 BOSS 所需攻击次数，即 $\lceil \frac{HP}{x}\rceil \backslash lceil\; \backslash frac\{HP\}\{x\}\; \backslash rceil$，若这个值超过 $2n2n$ 直接输出 -1。

在第 $ii$ 回合开始时，我们首先令前 $i-1i-1$ 回合全部防御，然后考虑每次进行一步令 BOSS 生命值减 $11$ 的操作。

操作方法有 2 种：

1. 放弃第 $xx$ 次防御进行输出，受到 $a[x]-a[x]\mathrm{/}2a[x]-a[x]/2$ 伤害。
2. 在某次放弃防御的基础上狂暴，受到 $yy$ 伤害。

令优先队列里存放的是 “目前想要实施的放弃防御操作所受的代价” ，那么想干掉 boss ，算上下一次的普通攻击与狂暴，优先队列中至少要存放 $\lceil (hp-2)\mathrm{/}2\rceil \backslash lceil\; (hp-2)/2\; \backslash rceil$ 个数。

而在能够 pop 的情况下，对于放弃防御操作而言，如果其代价大于 $yy$ ，那么这次操作显然不如进行狂暴，因此将其 pop。

同时，如果 “优先队列中的操作数“ 加上 “下回合的一次普通攻击操作“ 大于 $hphp$，也需要进行pop。

于是令优先队列内数值和为 $qSumqSum$，数值个数为 $qNumqNum$，得到第 $ii$ 回合的最优解为：$1+{\sum }_1^{i-1}\frac{a[i]}{2}1+\backslash sum\_1^\{i-1\}\; \backslash frac\{a[i]\}\{2\}$ $++$ $qSumqSum$ $++$ $(hp-1-qNum)\ast y(hp-1-qNum)*y$。

对每回合取 min 即为答案。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int i,j,k,t,n,m;
ll hp,x,y,a[200500],sum,s,res,tmp;

priority_queue<ll> q;

int main(){
	cin.tie(0);
	cin>>t;
	while(t--){
		cin>>hp>>x>>y>>n;
		for(i=1;i<=n;i++)cin>>a[i];
		
		hp=(hp+x-1)/x;tmp=hp;
		
		if(2ll*n<hp){
			cout<<"-1\n";continue;
		}
		
		while(!q.empty())q.pop();
		s=sum=0;res=1e18;
		
		for(i=1;i<=n;i++){
			if(q.size()*2+2>=hp){
				res=min(res,1+sum+s+(hp-(ll)q.size()-1)*y);
			}
			sum+=a[i]/2;
			s+=(a[i]-a[i]/2);
			q.push(a[i]-a[i]/2);
			while((ll)q.size()*2>=hp&&q.top()>y||q.size()>=hp){
				s-=q.top();q.pop();
			}
		}
		cout<<res<<'\n';
	}
}