自动搬运

查看原文

来自洛谷，原作者为

	KingBenQi **

搬运于2025-08-24 21:26:23，当前版本为作者最后更新于2018-02-23 22:04:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

Solution

只是本人自己的代码,果然很弱 这道题就是我的忍者们都看成一个单独的堆 对于每个忍者我们对进行相应的枚举,把他的当作领导节点 考虑对每个节点建堆,对于每个非叶节点,将该节点与每个儿子节点合并(左偏树),维护堆中节点数和堆中节点的点权和

#include<bits/stdc++.h>
#define LL long long
#define N 100005
using namespace std;
inline int gi(){
    char ch=getchar();int x=0,q=0;
    while(ch<'0' || ch>'9') ch=='-'?q=1:0,ch=getchar();
    while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
    return q?(-x):x;
}
struct Player{
	int fa,cost,lead;
}R[N<<2];
int n,m;
LL ans;
int size[N],root[N],dis[N],ls[N],rs[N];
LL sum[N];
void BuildHeap(int now){
	size[now]=1;
	root[now]=now;
	sum[now]=R[now].cost;
}
int Merge(int A,int B){
	if(!A||!B) return A+B;
	if(R[A].cost<R[B].cost) swap(A,B);
	rs[A]=Merge(rs[A],B);
	if(dis[ls[A]]<dis[rs[A]]) swap(ls[A],rs[A]);
	dis[A]=dis[rs[A]]+1;
	return A;
}
int main(){
	//freopen("Master.in","r",stdin);
	//freopen("Master.out","w",stdout);
	n=gi();m=gi();
	for(int i=1,b,c,l;i<=n;i++){
		b=gi();c=gi();l=gi();
		R[i]=(Player){b,c,l};
		ans=max((LL)(R[i].lead),ans);
		BuildHeap(i);    //每个忍者看成一个单独的堆
	}
	for(int i=n;i>1;i--){
		int fa=R[i].fa;          //当前的忍者看作为领导,对每个点都进行枚举
		root[fa]=Merge(root[i],root[R[i].fa]);      //合并当前节点和本身的父亲节点
		size[fa]+=size[i];sum[fa]+=sum[i];        //把当前的元素加到父亲数size和sum都想应改变
		while(sum[fa]>m){
			sum[fa]-=R[root[fa]].cost;      //如果超过了删除堆顶元素
			root[fa]=Merge(ls[root[fa]],rs[root[fa]]);     
			size[fa]--;    //更新size
		}
		ans=max(ans,(LL)(R[fa].lead)*(LL)(size[fa]));   //取max的ans
	}
	cout<<ans<<endl;
	return 0;
}