大型网站过程,昭通网站建设兼职,广东省广州市白云区白云湖街道,建网站需要哪些条件Description 在一个忍者的帮派里#xff0c;一些忍者们被选中派遣给顾客#xff0c;然后依据自己的工作获取报偿。在这个帮派里#xff0c;有一名忍者被称之为 Master。除了 Master以外#xff0c;每名忍者都有且仅有一个上级。为保密#xff0c;同时增强忍者们的领导力一些忍者们被选中派遣给顾客然后依据自己的工作获取报偿。在这个帮派里有一名忍者被称之为 Master。除了 Master以外每名忍者都有且仅有一个上级。为保密同时增强忍者们的领导力所有与他们工作相关的指令总是由上级发送给他的直接下属而不允许通过其他的方式发送。现在你要招募一批忍者并把它们派遣给顾客。你需要为每个被派遣的忍者 支付一定的薪水同时使得支付的薪水总额不超过你的预算。另外为了发送指令你需要选择一名忍者作为管理者要求这个管理者可以向所有被派遣的忍者 发送指令在发送指令时任何忍者不管是否被派遣都可以作为消息的传递 人。管理者自己可以被派遣也可以不被派遣。当然如果管理者没有被排遣就不需要支付管理者的薪水。你的目标是在预算内使顾客的满意度最大。这里定义顾客的满意度为派遣的忍者总数乘以管理者的领导力水平其中每个忍者的领导力水平也是一定的。写一个程序给定每一个忍者 i的上级 Bi薪水Ci领导力L i以及支付给忍者们的薪水总预算 M输出在预算内满足上述要求时顾客满意度的最大值。 1 ≤N ≤ 100,000 忍者的个数 1 ≤M ≤ 1,000,000,000 薪水总预算 0 ≤Bi i 忍者的上级的编号 1 ≤Ci ≤ M 忍者的薪水 1 ≤Li ≤ 1,000,000,000 忍者的领导力水平。 Input 从标准输入读入数据。 第一行包含两个整数 N和 M其中 N表示忍者的个数M表示薪水的总预算。 接下来 N行描述忍者们的上级、薪水以及领导力。其中的第 i 行包含三个整 Bi , C i , L i分别表示第i个忍者的上级薪水以及领导力。Master满足B i 0并且每一个忍者的老板的编号一定小于自己的编号 Bi i。 Output 输出一个数表示在预算内顾客的满意度的最大值。 Sample Input 5 4 0 3 3 1 3 5 2 2 2 1 2 4 2 3 1 Sample Output 6 HINT 如果我们选择编号为 1的忍者作为管理者并且派遣第三个和第四个忍者薪水总和为 4没有超过总预算 4。因为派遣了 2 个忍者并且管理者的领导力为3用户的满意度为 2,是可以得到的用户满意度的最大值。 我们需要处理出每个节点的孩子中满足条件的尽可能多的节点但是我们如果从上往下遍历处理的话显然会超时O(n^2)。
所以我们需要从下往上进行处理尽可能地利用以前的信息所以不妨对每个节点使用一个优先队列将满足条件的都放进去如果工资已经高于能负担的工资就把工资最高的那个人去掉。然后将相邻两个节点进行合并。为了提高效率我们应当先处理重孩子再处理轻孩子。
可是这样使用STL自带的优先队列复杂度还不够优秀我们可以针对这个问题实现我们自己的优先队列所用的数据结构就是左偏树
左偏树是一种二叉堆这种堆可以合并出高度比较低的树具体就是通过节点x到没有右子树的节点y的距离来进行判断及时交换左右孩子从而使得堆不会变得很长。
这样的堆有利于再和其他的堆进行合并。
合并的时候从上往下合并不断地把根节点更大的右儿子和另一个堆合并。可以证明这样的复杂度最优秀
具体到这个问题中我们用节点类型存储每个节点的数据可是每个节点的根节点却不一定是他本身在二叉堆构造过程中原本的位置已经改变为了记录这种改变我们用root数组记录在左偏树中该节点的父亲节点。在访问到他为止左偏树中的节点都是实际树形关系中他的孩子和他本身
当目前工资已经超过最大工资的时候我们就删去堆顶元素贪心思想堆顶的工资最高删去他最划算
借鉴了网上的代码加上自己的思考发现自己这样写虽然没有什么错误但是还是应该把用于记录堆关系的和用于记录树关系的数据分开混在一起导致容易理解错误。
#includeiostream
#includecstring
#includecstdio
#includeclimits
#includealgorithm
#includectime
#includecstdlib
#includequeue
#includeset
#includemap
#includecmath
#define rep(i,x,n) for(register int ix;in;i) using namespace std;typedef long long ll;
const int MAXN1e55;
struct Node
{int cost; ll ctrl;int rson,lson,dis;
}Tree[MAXN];
int nex[MAXN];
int head[MAXN],num0;
int N; ll M;
int root[MAXN],sz[MAXN]; ll sum[MAXN];
ll ans0;int Merge(int x,int y)
{if(!x || !y) return xy;if(Tree[x].costTree[y].cost) swap(x,y);Tree[x].rsonMerge(Tree[x].rson,y);if(Tree[Tree[x].rson].dis Tree[Tree[x].lson].dis) swap(Tree[x].rson,Tree[x].lson);Tree[x].disTree[Tree[x].rson].dis1;return x;
}void Delete(int x)
{xMerge(Tree[x].lson,Tree[x].rson);
}int dfs(int x)
{root[x]x;sum[x]Tree[x].cost; sz[x]1;for(int ihead[x];i;inex[i]){dfs(i);root[x]Merge(root[x],root[i]);sum[x]sum[i]; sz[x]sz[i];}while(sum[x]M){sum[x]-Tree[root[x]].cost;sz[x]--;Delete(root[x]);}ansmax(ans,sz[x]*Tree[x].ctrl);
}int main()
{scanf(%d%lld,N,M);int t; //int Master-1;rep(i,1,N){scanf(%d,t);//if(t0) Masteri;nex[i]head[t]; head[t]i;scanf(%d%lld,Tree[i].cost,Tree[i].ctrl);}dfs(1);printf(%lld,ans);return 0;
}
