本文主要是介绍51nod1307 绳子与重物，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
有N条绳子编号 0 至 N - 1，每条绳子后面栓了一个重物重量为Wi，绳子的最大负重为Ci。每条绳子或挂在别的绳子下或直接挂在钩子上（编号-1）。如果绳子下所有重物的重量大于绳子的最大负重就会断掉（等于不会断）。依次给出每条绳子的负重Ci、重物的重量Wi以及绳子会挂在之前的哪条绳子的下面，问最多挂多少个绳子而不会出现绳子断掉的情况。
例如下图：
5, 2, -1
3, 3, 0
6, 1, -1
3, 1, 0
3, 2, 3
挂到第4个时会有绳子断掉，所以输出3。
第2 - N + 1行：每行3个数，Ci, Wi, Pi，Ci表示最大负重，Wi表示重物的重量，Pi表示挂在哪个绳子上，如果直接挂在钩子上则Pi = -1（1 <= Ci <= 10^9，1 <= Wi <= 10^9，-1 <= Pi <= N - 2)。
5 5 2 -1 3 3 0 6 1 -1 3 1 0 3 2 3
3
从后往前将重物挂上去
因为当处理到i时，所有i的孩子都已经挂在i上了
这时如果以i为根的子树重量sum[i]>c[i]
则从最后一个重物开始删除重物 直到sum[i]<=c[i]
如果使用并查集维护par[i]=i的根
每次删除x 就等价于sum[find(x)]-=w[x]
每个重物最多最多被挂一次，被删一次 复杂度O(n)
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
struct node
{int w,p,c,sum;
} std1[100000];
int f[541000];
int find(int r)
{if(r==f[r])return f[r];else{f[r]=find(f[r]);return f[r];}
}
int main()
{int n,i,j;scanf("%d",&n);for(i=1; i<=n; i++){scanf("%d %d %d",&std1[i].c,&std1[i].w,&std1[i].p);std1[i].sum+=std1[i].w;std1[i].p++;f[i]=i;}long long ans=n;for(i=n; i>=1; i--){while(std1[i].sum>std1[i].c){int k=find(ans);std1[k].sum-=std1[ans].w;ans--;}std1[std1[i].p].sum+=std1[i].sum;f[i]=std1[i].p;}printf("%lld\n",ans);return 0;
}
这篇关于51nod1307 绳子与重物的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
