題目描述
牛半仙的妹子被大魔王抓走了，牛半仙為了就他的妹子，前往攻打魔塔，
魔塔為一棵樹，牛半仙初始在一號點，
牛半仙有攻擊，防御，血量三個屬性，
除一號點外每個點都有魔物防守，魔物也有攻擊，防御，血量三個屬性，
每個怪物后面都守著一些藍寶石，獲得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?1?bi?)
總傷害為 ∑ 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=1n?hi?×(攻擊?初始防御?∑j=1i?1?bi?)
求這個的最小值 即求 ∑ 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=1n?hi?×∑j=1i?1?bi? 的最大值
可以推出按照權值 t i = h i b i t_i=\dfrac{h_i}{b_i} ti?=bi?hi?? 升序排出來的答案最優
證明：若最優的情況為： 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}} bi?hi??<bi+1?hi+1?? 得證 （感性理解也可）
考慮貪心 我們先攻擊 t i t_i ti? 小的 再攻擊大的
顯然不行 比如一個 t i t_i ti?大的點有很多 $ t_i$ 小的子節點
這里給出一個結論
若兒子節點
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?+b2?h1?+h2??和 h 3 b 3 \dfrac{h_3}{b_3} b3?h3?? 的大小 所以大點的權值為 ∑ 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 <bits/stdc++.h>
#define N 210000
using 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<node> 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<n;i++){ scanf("%lld %lld",&x,&y); add(x,y); add(y,x); }
scanf("%lld %lld %lld",&ans,&a,&b); fa[1]=1;
h[1].siz=b;
for(int i=2;i<=n;i++){
fa[i]=i;
scanf("%lld %lld %lld %lld",&z,&x,&y,&h[i].siz);
h[i].val=z/(a-y); if(z%(a-y)!=0)h[i].val++;
h[i].val--;
ans-=(x-b)*h[i].val;
h[i].pos=i;
q.push(h[i]);
}
dfs(1);
node u;
while(!q.empty()){
u=q.top(); q.pop(); x=u.pos;
if(tag[x])continue; tag[x]=1;
y=findf(ff[x]);
ans+=h[y].siz*h[x].val;
h[y].val+=h[x].val; h[y].siz+=h[x].siz;
if(y!=1&&tag[y]==0)q.push(h[y]);
fa[x]=y;
}
cout<<ans;
}
講得不清楚就問哦 畢竟蒟蒻描述能力真的…不太好
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/189128.html
標籤：其他
上一篇：同程藝龍面經
下一篇：bilibili首頁導航