本文共 3352 字，大约阅读时间需要 11 分钟。

题目描述

牛半仙的妹子被大魔王抓走了，牛半仙为了就他的妹子，前往攻打魔塔。

魔塔为一棵树，牛半仙初始在一号点。

牛半仙有攻击，防御，血量三个属性。

除一号点外每个点都有魔物防守，魔物也有攻击，防御，血量三个属性。

每个怪物后面都守着一些蓝宝石，获得1蓝宝石可增加1防。

牛半仙具有突袭属性，所以遇到魔物后会率先发动攻击，然后牛半仙和魔物轮换地攻击对方。

一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。

当一个角色的血量小于等于 0 时，他就会死亡。

当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。

当一个魔物死亡后，这个魔物所在的节点就不会再产生新的魔物。

现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。

输入描述:

第一行一个 n 代表节点数。 随后 n-1 行，每行两个数 i,j，表示 i 与 j 节点有边相连。

随后一行，三个数，依次为勇士的血量、攻击、防御。 随后 n-1 行，每行四个数，依次为怪物的血量、攻击、防御，和其守着的蓝宝石数量。

输出描述:

一个数，代表最大血量。如果牛半仙在打死魔塔的所有魔物之前就已经死亡了，则输出 -1。

备注:

对于100%的数据:$n\le 10^5$，树

对于100%的数据：有牛半仙血量$<5\ast 10^{18}$，攻击$=2000$，盔甲防御$=0$。怪物血量为$3000$ ~

$10^6$，攻击$5\times 10^5$−$7\times 10^5$，防御$\le 1000$，打完一只怪后获得的蓝宝石数量为$1$至$5$

官方题解看懂 自己琢磨了一下想通了

考虑第$i$个攻击的怪

记第$i$个怪有$b_i$个蓝宝石

因为怪的血量和攻击和防御是不变的 勇士的攻击也是不变的

所以它会被勇士攻击 $\lceil \frac{血量}{勇士攻击-防御}\rceil$ 轮

并攻击勇士$\lceil \frac{血量}{勇士攻击-防御}\rceil -1$ 轮 可直接求出 记为 $h_i$

造成的伤害为 $h_i\times (攻击-初始防御-{\sum }_{j=1}^{i-1}{b}_i)$

总伤害为${\sum }_{i=1}^n{h}_i\times (攻击-初始防御-{\sum }_{j=1}^{i-1}{b}_i)$

求这个的最小值 即求 ${\sum }_{i=1}^n{h}_i\times {\sum }_{j=1}^{i-1}{b}_i$ 的最大值

可以推出按照权值 $t_i=\frac{h_i}{b_i}$ 升序排出来的答案最优

证明：若最优的情况为：$h_1,h_2...h_n$ 。 交换 $i$, $i+1$答案的改变量是 $h_i\times b_{i+1}-h_{i+1}\times b_i<0$

即 $\frac{h_i}{b_i}<\frac{h_{i+1}}{b_{i+1}}$ 得证 （感性理解也可）

考虑贪心 我们先攻击 $t_i$ 小的 再攻击大的

显然不行 比如一个$t_i$大的点有很多 $t_i$ 小的子节点

这里给出一个结论

根据这个结论 我们可以从权值最小的节点开始 若节点 $y$ 的权值小于父亲 $x$

这个大点的权值 $t$ 变成 $\frac{\sum h_i}{\sum b_i}$

证明：若$1$号节点和$2$节点要连续攻击 比较下面两种情况对答案的贡献

① 按$1,2,3$ 排 $h_2\times b_1+h_3\times (b_1+b_2)$

② 按$3,1,2$ 排 $h_1\times b_3+h_2\times (b_3+b_1)$

①-②得 $h_3(b_1+b_2)-(h_1+h_2)b_3$

比较答案大小即比较的是$\frac{h_1+h_2}{b_1+b_2}$和$\frac{h_3}{b_3}$ 的大小 所以大点的权值为 $\frac{\sum h_i}{\sum b_i}$ 得证

从权值最小的节点开始 若点 $y$ 的权值小于父亲所在的大点 $x$ 就把 $y$ 合并到 $x$ 上 合并成一个大点

处理完后就从根节点开始 贪心地选择可以到达点中 权值最小的点

所形成的顺序就是攻击怪物的顺序了

#include 
   
    #define N 210000using namespace std;typedef long long ll;int n;int f[N],nxt[N],data[N],num,fa[N],ff[N];ll ans;bool tag[N];struct node{   	ll val,siz,pos;}h[N];inline bool operator <(node x,node y){    return 1ll*x.val*y.siz>1ll*y.val*x.siz; }inline void add(int x,int y){    nxt[++num]=f[x]; f[x]=num; data[num]=y; }priority_queue
    
      q;inline int findf(int x){    return fa[x]==x?x:fa[x]=findf(fa[x]); }inline void dfs(int x){   	int y;	for(int i=f[x];i;i=nxt[i]){   		y=data[i]; if(y==ff[x])continue;		ff[y]=x; dfs(y); 	}}int main(){   	cin>>n;	ll x,y,z,a,b;	for(int i=1;i
    
   

讲得不清楚就问哦 毕竟蒟蒻描述能力真的…不太好

转载地址：http://yahl.baihongyu.com/