郑州网站外包哪家好,商家联盟会员管理系统,公司网站建设指南,山东网站建设培训题意#xff1a;一个魔塔游戏的地图是一棵以 111 为根的树#xff0c;起点为根#xff0c;除根外每个结点有一个怪物#xff0c;给定每个怪物血量、攻击、防御、奖励蓝宝石个数#xff08;加防御#xff09;#xff0c;勇士的血量、攻击、防御#xff0c;遇到怪物必须战…题意一个魔塔游戏的地图是一棵以 111 为根的树起点为根除根外每个结点有一个怪物给定每个怪物血量、攻击、防御、奖励蓝宝石个数加防御勇士的血量、攻击、防御遇到怪物必须战斗勇士永远先手求击败所有怪物后最多剩余血量。
n≤105n\leq 10^5n≤105所有战斗防御小于攻击。
由于不能加攻击所以打败一个怪物受到的攻击次数是固定的算出来记为 kik_iki奖励宝石记为 bib_ibi。而每获得一个宝石可以让之后的所有怪物减伤 kik_iki。
先考虑菊花图也就是没有顺序限制。
考虑一个解 {p1,p2,p3,…,pn}\{p_1,p_2,p_3,\dots,p_n\}{p1,p2,p3,…,pn} 如果交换 pi,pi1p_i,p_{i1}pi,pi1 让解变优即
dkpi(ddpi)kpi1dkpi1(ddpi1)kpidk_{p_i}(dd_{p_i})k_{p_{i1}}dk_{p_{i1}}(dd_{p_{i1}})k_{p_i}dkpi(ddpi)kpi1dkpi1(ddpi1)kpi
dpikpidpi1kpi1\frac{d_{p_i}}{k_{p_i}}\frac{d_{p_{i1}}}{k_{p_{i1}}}kpidpikpi1dpi1
所以在没有先决条件的情况下按 diki\frac{d_i}{k_i}kidi 从小到大排序一个个选就可以了。定义性价比为 cidikic_i\frac{d_i}{k_i}cikidi。
考虑树的情况删除点 uuu 后要么继续删儿子要么删其他点废话
如果 uuu 性价比最高的儿子 vvv 性价比比 uuu 高那么显然一定会继续删 vvv 。
所以我们可以把 u,vu,vu,v 合并成一个点 d、kd、kd、k 相加重新计算性价比。这时候 uuu 的其他儿子需要与合并后的点比较。
实现的时候把所有怪物压进按性价比排序的大根堆每次选出最大的如果父亲性价比比它低也就是还在堆里就和父亲合并否则删掉这个点所在的大点可以用并查集实现。
复杂度 O(nlogn)O(n\log n)O(nlogn)
#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 ans0;char cgetchar();while (!isdigit(c)) cgetchar();while (isdigit(c)) ans(ans3)(ans1)(c^48),cgetchar();return ans;
}
vectorint 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 pairdouble,int pi;
priority_queuepi q;
ll pb,pa,pd;
int vis[MAXN],del[MAXN];
void dfs(int u,int f){fa[u]f;for (int i0;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],pdbns[u],del[u]1;for (int i0;i(int)son[u].size();i) dfs(son[u][i]);
}
int main()
{int nread();for (int i1;in;i){int u,v;uread(),vread();e[u].push_back(v),e[v].push_back(u);}pbread(),paread(),pdread();for (int i2;in;i){int bl,d;blread(),a[i]read(),dread(),bns[i]b[i]read();cnt[i]k[i](bl-1)/(pa-d);}dfs(1,0);for (int i2;in;i) q.push(make_pair(1.0*b[i]/k[i],rt[i]i));del[1]1;while (!q.empty()){int uq.top().second;q.pop();if (vis[u]) continue;vis[u]true;if (del[fa[u]]) dfs(u);else{int ffind(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 (pb0) pb-1;coutpb;return 0;
}
