本文共 3352 字,大约阅读时间需要 11 分钟。
题目描述
牛半仙的妹子被大魔王抓走了,牛半仙为了就他的妹子,前往攻打魔塔。
魔塔为一棵树,牛半仙初始在一号点。
牛半仙有攻击,防御,血量三个属性。
除一号点外每个点都有魔物防守,魔物也有攻击,防御,血量三个属性。
每个怪物后面都守着一些蓝宝石,获得1蓝宝石可增加1防。
牛半仙具有突袭属性,所以遇到魔物后会率先发动攻击,然后牛半仙和魔物轮换地攻击对方。
一个角色被攻击一次减少的血量是对方的攻击减去自己的防御。
当一个角色的血量小于等于 0 时,他就会死亡。
当牛半仙第一次到达某个节点时会与这个节点的魔物发生战斗。
当一个魔物死亡后,这个魔物所在的节点就不会再产生新的魔物。
现在牛半仙想知道他打死魔塔的所有魔物后的最大血量。
输入描述:
第一行一个 n 代表节点数。 随后 n-1 行,每行两个数 i,j,表示 i 与 j 节点有边相连。
随后一行,三个数,依次为勇士的血量、攻击、防御。 随后 n-1 行,每行四个数,依次为怪物的血量、攻击、防御,和其守着的蓝宝石数量。输出描述:
一个数,代表最大血量。如果牛半仙在打死魔塔的所有魔物之前就已经死亡了,则输出 -1。
备注:
对于100%的数据: n ≤ 1 0 5 n \le 10^5 n≤105,树
对于100%的数据:有牛半仙血量 < 5 ∗ 1 0 18 <5*10^{18} <5∗1018,攻击 = 2000 =2000 =2000,盔甲防御 = 0 =0 =0。怪物血量为 3000 3000 3000 ~ 1 0 6 10^6 106,攻击 5 × 1 0 5 5×10^5 5×105− 7 × 1 0 5 7\times 10^5 7×105,防御 ≤ 1000 \leq 1000 ≤1000,打完一只怪后获得的蓝宝石数量为 1 1 1至 5 5 5
官方题解看懂 自己琢磨了一下想通了
所以写个通俗 ju ruo 点儿的考虑第 i i i个攻击的怪
记第 i i i个怪有 b i b_i bi个蓝宝石
因为怪的血量和攻击和防御是不变的 勇士的攻击也是不变的
所以它会被勇士攻击 ⌈ 血 量 勇 士 攻 击 − 防 御 ⌉ \lceil\dfrac{血量}{勇士攻击-防御}\rceil ⌈勇士攻击−防御血量⌉ 轮
并攻击勇士 ⌈ 血 量 勇 士 攻 击 − 防 御 ⌉ − 1 \lceil\dfrac{血量}{勇士攻击-防御}\rceil -1 ⌈勇士攻击−防御血量⌉−1 轮 可直接求出 记为 h i h_i hi
造成的伤害为 h i × ( 攻 击 − 初 始 防 御 − ∑ j = 1 i − 1 b i ) h_i\times (攻击-初始防御-\sum_{j=1}^{i-1}b_i) hi×(攻击−初始防御−∑j=1i−1bi)
总伤害为 ∑ i = 1 n h i × ( 攻 击 − 初 始 防 御 − ∑ j = 1 i − 1 b i ) \sum_{i=1}^n h_i\times (攻击-初始防御-\sum_{j=1}^{i-1}b_i) ∑i=1nhi×(攻击−初始防御−∑j=1i−1bi)
求这个的最小值 即求 ∑ i = 1 n h i × ∑ j = 1 i − 1 b i \sum_{i=1}^n h_i\times \sum_{j=1}^{i-1}b_i ∑i=1nhi×∑j=1i−1bi 的最大值
可以推出按照权值 t i = h i b i t_i=\dfrac{h_i}{b_i} ti=bihi 升序排出来的答案最优
证明:若最优的情况为: h 1 , h 2 . . . h n h_1,h_2...h_n h1,h2...hn 。 交换 i i i, i + 1 i+1 i+1答案的改变量是 h i × b i + 1 − h i + 1 × b i < 0 h_i\times b_{i+1}-h_{i+1}\times b_i<0 hi×bi+1−hi+1×bi<0
即 h i b i < h i + 1 b i + 1 \dfrac{h_i}{b_i}<\dfrac{h_{i+1}}{b_{i+1}} bihi<bi+1hi+1 得证 (感性理解也可)
考虑贪心 我们先攻击 t i t_i ti 小的 再攻击大的
显然不行 比如一个 t i t_i ti大的点有很多 t i t_i ti 小的子节点
这里给出一个结论
若儿子节点 y y y 的 t t t 小于父亲节点 x x x 的 t t t 那么攻击了的父亲节点 x x x 过后 会立即攻击儿子 y y y (这里好好想想为什么)根据这个结论 我们可以从权值最小的节点开始 若节点 y y y 的权值小于父亲 x x x
这就意味着会连续攻击 x , y x,y x,y 我们就把 y y y 合并到 x x x 上 合并成一个大点这个大点的权值 t t t 变成 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} ∑bi∑hi
证明:若 1 1 1号节点和 2 2 2节点要连续攻击 比较下面两种情况对答案的贡献
① 按 1 , 2 , 3 1,2,3 1,2,3 排 h 2 × b 1 + h 3 × ( b 1 + b 2 ) h_2\times b_1+h_3\times (b_1+b_2) h2×b1+h3×(b1+b2)
② 按 3 , 1 , 2 3,1,2 3,1,2 排 h 1 × b 3 + h 2 × ( b 3 + b 1 ) h_1\times b_3+h_2\times (b_3+b_1) h1×b3+h2×(b3+b1)
①-②得 h 3 ( b 1 + b 2 ) − ( h 1 + h 2 ) b 3 h_3(b_1+b_2)-(h_1+h_2)b_3 h3(b1+b2)−(h1+h2)b3
比较答案大小即比较的是 h 1 + h 2 b 1 + b 2 \dfrac{h_1+h_2}{b_1+b_2} b1+b2h1+h2和 h 3 b 3 \dfrac{h_3}{b_3} b3h3 的大小 所以大点的权值为 ∑ h i ∑ b i \dfrac{\sum h_i}{\sum b_i} ∑bi∑hi 得证
从权值最小的节点开始 若点 y y y 的权值小于父亲所在的大点 x x x 就把 y y y 合并到 x x 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/