題目描述
牛半仙的妹子被大魔王抓走了，牛半仙為了就他的妹子，前往攻打魔塔。
魔塔為一棵樹，牛半仙初始在一號點。
牛半仙有攻擊，防禦，血量三個屬性。
除一號點外每個點都有魔物防守，魔物也有攻擊，防禦，血量三個屬性。
每個怪物後面都守著一些藍寶石，獲得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$ 小的子節點
這裡給出一個結論
若兒子節點
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 <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;
}
講得不清楚就問哦 畢竟蒟蒻描述能力真的…不太好