【牛客NOIP模拟】牛半仙的魔塔(增强版)【贪心】【并查集】
题意:一个魔塔游戏的地图是一棵以 1 1 1 为根的树,起点为根,除根外每个结点有一个怪物,给定每个怪物血量、攻击、防御、奖励蓝宝石个数(加防御),勇士的血量、攻击、防御,遇到怪物必须战斗,勇士永远先手,求击败所有怪物后最多剩余血量。
n ≤ 1 0 5 n\leq 10^5 n≤105,所有战斗防御小于攻击。
由于不能加攻击,所以打败一个怪物受到的攻击次数是固定的,算出来记为 k i k_i ki,奖励宝石记为 b i b_i bi。而每获得一个宝石可以让之后的所有怪物减伤 k i k_i ki。
先考虑菊花图,也就是没有顺序限制。
考虑一个解 { p 1 , p 2 , p 3 , … , p n } \{p_1,p_2,p_3,\dots,p_n\} {p1,p2,p3,…,pn} ,如果交换 p i , p i + 1 p_i,p_{i+1} pi,pi+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 dk_{p_i}+(d+d_{p_i})k_{p_{i+1}}<dk_{p_{i+1}}+(d+d_{p_{i+1}})k_{p_i} dkpi+(d+dpi)kpi+1<dkpi+1+(d+dpi+1)kpi
d p i k p i < d p i + 1 k p i + 1 \frac{d_{p_i}}{k_{p_i}}<\frac{d_{p_{i+1}}}{k_{p_{i+1}}} kpidpi<kpi+1dpi+1
所以在没有先决条件的情况下,按 d i k i \frac{d_i}{k_i} kidi 从小到大排序一个个选就可以了。定义性价比为 c i = d i k i c_i=\frac{d_i}{k_i} ci=kidi。
考虑树的情况,删除点
u
u
u 后,要么继续删儿子,要么删其他点废话
如果 u u u 性价比最高的儿子 v v v 性价比比 u u u 高,那么显然一定会继续删 v v v 。
所以我们可以把 u , v u,v u,v 合并成一个点, d 、 k d、k d、k 相加重新计算性价比。这时候 u u u 的其他儿子需要与合并后的点比较。
实现的时候把所有怪物压进按性价比排序的大根堆,每次选出最大的,如果父亲性价比比它低(也就是还在堆里)就和父亲合并,否则删掉这个点所在的大点,可以用并查集实现。
复杂度 O ( n log n ) 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 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;
}
本文地址:https://blog.csdn.net/luositing/article/details/109239171
上一篇: 春困催生心理焦虑