P1485火枪打怪（题解）

发表于 | 更新于 | 阅读次数：
本文字数： 6.8k | 阅读时长 ≈ 6 分钟

这里有一篇题解。

P1485火枪打怪（题解）

点我

PS.

此题第一眼就可以看出是二分答案
我看了标签QwQ

Solution.

最难的是二分的$\texttt{check}$函数如何写。
首先因为子弹的威力是定值，所以每一个子弹的溅射范围是一样的，事先算出溅射范围。
$\texttt{p-(i-j)}\times\texttt{(i-j)}=\texttt{p-i}^\texttt{2}+\texttt{2}\times\texttt{i}\times\texttt{j+j}^\texttt{2}$
这个式子中，$\texttt{i}^\texttt{2}$、$\texttt{2}\times\texttt{i}\times\texttt{j}$、$\texttt{j}^\texttt{2}$ 都是可以维护的。
于是我们维护$\texttt{i}^\texttt{2}$之和，$\texttt{2}\times\texttt{i}$之和，$\texttt{1}$之和。
在加入时可以临时乘上$\texttt{j}$的次方次幂。

Coding.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<bits/stdc++.h>
#define ll long long
#define int long long
using namespace std;
int n,k,b[500005];
ll a[500005];
inline char check(ll p)
{
	ll _2=0,_1=0,_0=0,s=sqrt(p)+1;
	//s表示溅射范围，_2，_1，_0分别表示 i*i ， 2*i ， 1 。
	int tot=0;
	//tot表示子弹数。
	memset(b,0,sizeof(b));
	//b表示在这里有无发过子弹。
	for(int i=n;i>=1;i--)
	{
		if(i+s<=n&&b[i+s]) _2-=(i+s)*(i+s)*b[i+s],_1-=(i+s)*b[i+s],_0-=b[i+s];
		//溅射结束，去掉影响。
		ll gone=_0*p-_0*i*i+2*_1*i-_2;
		//gong表示这个怪物由于之前的溅射扣的血量。
		if(a[i]>=gone) b[i]=(a[i]-gone)/p+1,tot+=b[i],_0+=b[i],_1+=b[i]*i,_2+=b[i]*i*i;
		//如果这个怪物没被打死，还需要在开枪。
		if(tot>k) return 1;
		//k枪已经打不死全部怪物了。
	}
	return 0;
}
signed main()
{
	scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++) scanf("%lld",a+i);
	ll l=1,r=1e13,ans=0;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(check(mid)) l=mid+1;else r=mid-1,ans=mid;
	}
	//二分板子。
	printf("%lld\n",ans);
	return 0;
}