題意：一個魔塔游戲的地圖是一棵以 $1$ 為根的樹，起點為根，除根外每個結點有一個怪物，給定每個怪物血量、攻擊、防御、獎勵藍寶石個數（加防御），勇士的血量、攻擊、防御，遇到怪物必須戰斗，勇士永遠先手，求擊敗所有怪物后最多剩余血量。

$n\le 10^5$，所有戰斗防御小于攻擊。

由于不能加攻擊，所以打敗一個怪物受到的攻擊次數是固定的，算出來記為 $k_i$，獎勵寶石記為 $b_i$。而每獲得一個寶石可以讓之后的所有怪物減傷 $k_i$。

先考慮菊花圖，也就是沒有順序限制。

考慮一個解 $\{p_1,p_2,p_3,\dots ,p_n\}$ ，如果交換 $p_i,p_{i+1}$ 讓解變優，即

$$d{k}_{p_i}+(d+d_{p_i})k_{p_{i+1}}<d{k}_{p_{i+1}}+(d+d_{p_{i+1}})k_{p_i}$$

$$\frac{d_{p_i}}{k_{p_i}}<\frac{d_{p_{i+1}}}{k_{p_{i+1}}}$$

所以在沒有先決條件的情況下，按 $\frac{d_i}{k_i}$ 從小到大排序一個個選就可以了。定義性價比為 $c_i=\frac{d_i}{k_i}$。

考慮樹的情況，刪除點 $u$ 后，要么繼續刪兒子，要么刪其他點廢話

如果 $u$ 性價比最高的兒子 $v$ 性價比比 $u$ 高，那么顯然一定會繼續刪 $v$ 。

所以我們可以把 $u,v$ 合并成一個點， $d、k$ 相加重新計算性價比。這時候 $u$ 的其他兒子需要與合并后的點比較。

實現的時候把所有怪物壓進按性價比排序的大根堆，每次選出最大的，如果父親性價比比它低（也就是還在堆里）就和父親合并，否則刪掉這個點所在的大點，可以用并查集實現。

復雜度 $O(n\log n)$

#include <iostream> #include <cstdio> #include <cstring> #include <cctype> #include <queue> #include <vector> #include <utility> #define MAXN 100005 using namespace std; typedef long long ll; inline ll read() {ll ans=0;char c=getchar();while (!isdigit(c)) c=getchar();while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();return ans; } vector<int> e[MAXN],son[MAXN]; int bns[MAXN],cnt[MAXN],a[MAXN],b[MAXN],k[MAXN]; int fa[MAXN],rt[MAXN]; int find(int x){return rt[x]==x? x:rt[x]=find(rt[x]);} typedef pair<double,int> pi; priority_queue<pi> q; ll pb,pa,pd; int vis[MAXN],del[MAXN]; void dfs(int u,int f){fa[u]=f;for (int i=0;i<(int)e[u].size();i++) if (e[u][i]!=f) dfs(e[u][i],u);} void dfs(int u) {pb-=(a[u]-pd)*cnt[u],pd+=bns[u],del[u]=1;for (int i=0;i<(int)son[u].size();i++) dfs(son[u][i]); } int main() {int n=read();for (int i=1;i<n;i++){int u,v;u=read(),v=read();e[u].push_back(v),e[v].push_back(u);}pb=read(),pa=read(),pd=read();for (int i=2;i<=n;i++){int bl,d;bl=read(),a[i]=read(),d=read(),bns[i]=b[i]=read();cnt[i]=k[i]=(bl-1)/(pa-d);}dfs(1,0);for (int i=2;i<=n;i++) q.push(make_pair(1.0*b[i]/k[i],rt[i]=i));del[1]=1;while (!q.empty()){int u=q.top().second;q.pop();if (vis[u]) continue;vis[u]=true;if (del[fa[u]]) dfs(u);else{int f=find(fa[u]);k[f]+=k[u],b[f]+=b[u];son[rt[u]=f].push_back(u);q.push(make_pair(1.0*b[f]/k[f],f));}}if (pb<=0) pb=-1;cout<<pb;return 0; }

總結

以上是生活随笔為你收集整理的【牛客NOIP模拟】牛半仙的魔塔（增强版）【贪心】【并查集】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。