题面

解析

看了好多dalao们的题解，然而还是不明白．．．

于是在想了半天后，决定自己写一篇题解。

step 1

首先,分析题意，

应该还是比较容易想到，

要一直攻击一个兵器，

直到破坏它为止。

因为迟早要把兵器都破坏完，但如果不先破坏一个的话，他就会一直攻击。

那么，就会有一个破坏兵器的先后顺序。

并且，注意到血量其实只是为了转化成攻击的次数，

因此可以用$d_i$表示$i$被攻击的次数，

另外，约定$a_i$为$i$的攻击力，

那么题目就分析完毕了！似乎说了一通废话

step 2

先考虑没有秒杀的情况，

那么，伤害最小，其实也就是$\sum_{i=1}^{n}$ $a_i$ $*$ ($\sum_{j=1}^{i}$-$1$) 最小，(注意，由于最后一次攻击时兵器已经被破坏了（题目描述有问题），因此要减$1$)

而对于两个相邻兵器$i$,$j$，

如果$i$排在$j$前面会更优，

并设$X$ $=$ $\sum_{k=1}^{i}d_k$，

则有不等式

$a_i$ $*$ ($X$-$1$)+$a_j $ $*$ ($X$$+$$d_i$ - $1$)$<$$a_j$ $*$ ($X$-$1$)+$a_i $ $*$ ($X$$+$$d_j$ - $1$)

那么，可以解得$d_i$$*$$a_j$$<$$d_j$$*$$a_i$，(自己解一下吧)

因此，将兵器按此规律排序，就是没有秒杀的最优解了似乎又是废话

但要计算出这个没有秒杀的最优解（后面要用）。

step 3

继续，在上一步的情况下考虑秒杀掉一个兵器，

设$v_i$为删除$i$后能减小的伤害，

那么对于排在$i$前面的兵器们，

在攻击他们的时候，$i$都会对基地造成伤害，

那么对于这一部分，减少的伤害就为($\sum_{j=1}^{i}$$d_j$-$1$)$*$$a_i$。

而对于排在$i$后面的所有兵器，

在攻击$i$时，

他们也在对基地造成伤害。

所以对于这一部分，减少的伤害为($\sum_{j=i+1}^{n}$$a_j$)$*$$d_i$。

综上，就可以得出$v_i$$=$($\sum_{j=1}^{i}$$d_j$-$1$)$*$$a_i$$+$($\sum_{j=i+1}^{n}$$a_j$)$*$$d_i$。

那么继续考虑秒杀两个兵器$i$，$j$，且$i$在$j$后面，

减少的伤害就是$v_i$$+$$v_j$$-$$a_i$$*$$d_j$(因为这一部分重复加了一次，所以减掉)。

然后，只要求出使$v_i$$+$$v_j$$-$$a_i$$*$$d_j$最大的$i$,$j$就行了。

step 4

那么怎么求呢？

对于每个$i$，

我们计算当它与顺序中前面的某个兵器一起被秒掉时，

能减少的伤害的最大值，

再算出$1$~$n$中这个式子最大的值就行了。

那么，我们要算出前面的兵器对它的影响，和它对后面的兵器的影响。

所以$CDQ$分治就成了解决问题的主要算法。

但还是无法解决问题啊！！！

到底要怎么算啊？

别着急，看我狂推公式【滑稽】。

首先我们设对于兵器$i$，我们已经找到了一个$j$和它一起秒杀(重复一遍，$j$在$i$前面)，

但是，却存在一个$k$能使答案更优，即：

$v_i$$+$$v_k$$-$$a_i$$*$$d_k$$>=$$v_i$$+$$v_j$$-$$a_i$$*$$d_j$

那么，约掉$v_i$，再移下项，就变成了：

($d_k$-$d_j$)$*$$a_i$$<=$$v_k$-$v_j$，

然后分类讨论：

$d_k$$>$$d_j$时，$a_i$$<=$$\frac{v_k-v_j}{d_k-d_j}$，
$d_k$$=$$d_j$时，$v_k$$>=$$v_j$，
$d_k$$<$$d_j$时，$a_i$$>=$$\frac{v_j-v_k}{d_j-d_k}$，

因此，我们只需要找到一个$j$，使得找不到$k$满足上面的式子，

那么这个$j$就是最优解了。

即：

设$y$是$i$的最优解，

那么对于任意满足$d_x$$<$$d_y$$<$$d_z$(等于时要特判)的$x$,$z$，

都有$\frac{v_y-v_x}{d_y-d_x}$$>$$a_i$$>$$\frac{v_y-v_z}{d_y-d_z}$，

因此，对于$l$~$mid$，我们先将$d$按升序排列，

再用单调队列维护$\frac{v_y-v_x}{d_y-d_x}$的降序排列(蒟蒻的单调队列讲得似乎有点不清楚自己理解下哈)

同时，对于$mid$+$1$~$r$为了节省时间，将$a$按降序排列(所以多开几个数组)，

每次在单调队列中找出第一个小于$a_i$的$\frac{v_y-v_x}{d_y-d_x}$，

再用$y$更新$i$的答案就行了。

对于$d$和$a$的排序，归并时排一下就可以解决。

具体实现方式看代码吧：

#include<bits/stdc++.h>

#define db double

#define ll long long

using namespace std;

inline int read(){

	ll sum=0,f=1;char ch=getchar();

	while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}

	return f*sum;

}

struct node{

	int a/*攻击*/,d/*被打次数*/;

	ll v/*被秒掉后下降的伤害*/;

}c[500001]/*敌方*/,q1[500001]/*按d升序排列*/,q2[500001]/*按a降序排列*/;

node qq[500001];//排序时临时存一下

int n,atk;

ll ans=0,ansn=0;

ll sa[500001]/*被打次数的前缀和*/,sb[500001]/*攻击的后缀和*/;

int q[500001];

bool cmp(node x,node y){

	return (ll)x.d*y.a<(ll)y.d*x.a;

}

db cmp1(int x,int y){

	if(q1[x].d==q1[y].d){

		if(q1[y].v<=q1[x].v) return 0;

		return 1e18;

	}

	return (db)((q1[y].v-q1[x].v)/(q1[y].d-q1[x].d));

}

void CDQ(int l,int r){

	if(l==r) return ;

	int mid=(l+r)>>1;

	CDQ(l,mid);CDQ(mid+1,r);

	int le=1,ri=0;

	for(int i=l;i<=mid;i++){

		while(le<ri&&cmp1(q[ri-1],q[ri])<cmp1(q[ri],i)) ri--;

		q[++ri]=i;

	}

	for(int i=mid+1;i<=r;i++){

		while(le<ri&&cmp1(q[le],q[le+1])>=q2[i].a) le++;

		ans=max(ans,(ll)(q2[i].v+q1[q[le]].v-q2[i].a*q1[q[le]].d));

	}

//--------------下面是排序

	int pi=l,qi=mid+1,tot=l;

	while(pi<=mid&&qi<=r){

		if(q1[pi].d<q1[qi].d) qq[tot++]=q1[pi++];

		else qq[tot++]=q1[qi++];

	}

	while(pi<=mid) qq[tot++]=q1[pi++];

	while(qi<=r) qq[tot++]=q1[qi++];

	for(int i=l;i<=r;i++) q1[i]=qq[i];

	pi=l,qi=mid+1,tot=l;

	while(pi<=mid&&qi<=r){

		if(q2[pi].a>q2[qi].a) qq[tot++]=q2[pi++];

		else qq[tot++]=q2[qi++];

	}

	while(pi<=mid) qq[tot++]=q2[pi++];

	while(qi<=r) qq[tot++]=q2[qi++];

	for(int i=l;i<=r;i++) q2[i]=qq[i];

}

int main(){

	freopen("fight.in","r",stdin);

	freopen("fight.out","w",stdout);

	n=read();atk=read();

	for(int i=1;i<=n;i++){

		c[i].a=read();c[i].d=read();

		c[i].d=(c[i].d-1)/atk+1;//转换为攻击的次数

	}

	sort(c+1,c+n+1,cmp);//无秒杀时的最优攻击顺序

	for(int i=1;i<=n;i++) sa[i]=sa[i-1]+c[i].d;//d的前缀和

	for(int i=n;i>=1;i--) sb[i]=sb[i+1]+c[i].a;//a的后缀和

	for(int i=1;i<=n;i++) ansn+=c[i].a*(sa[i]-1);//没有秒杀时的总伤害

	for(int i=1;i<=n;i++){

		c[i].v=(sa[i]-1)*c[i].a+sb[i+1]*c[i].d;

	}

	for(int i=1;i<=n;i++) q1[i]=c[i],q2[i]=c[i];

	CDQ(1,n);

	printf("%lld\n",ansn-ans);

	return 0;

}

巴特西

题解　【BZOJ4700】适者

题面

解析

step 1

step 2

step 3

step 4

最新文章

热门文章

巴特西

题解 【BZOJ4700】适者

题面