51Nod 1307 绳子与重物

Problem

有N条绳子编号 0 至 N - 1，每条绳子后面栓了一个重物重量为Wi，绳子的最大负重为Ci。每条绳子或挂在别的绳子下或直接挂在钩子上（编号-1）。如果绳子下所有重物的重量大于绳子的最大负重就会断掉（等于不会断）。依次给出每条绳子的负重Ci、重物的重量Wi以及绳子会挂在之前的哪条绳子的下面，问最多挂多少个绳子而不会出现绳子断掉的情况。

例如下图：

5, 2, -1 3, 3, 0 6, 1, -1 3, 1, 0 3, 2, 3

Solution

从n向1循环，设置一个n的尾指针，每次查询看是否超重，超重就尾指针向前，当前的减去去掉的那个，最后并查集合并到更高位。

Code

#include<stdio.h>
#include<iostream>
using namespace std;
#define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ll long long
int n;
struct E{
	int c,w,p;
}e[50020];
int f[50020];
ll sum[50020];
int find(int x){
	return f[x]==x?x:f[x]=find(f[x]);
}
int main(){
	//io_opt;
	scanf("%d",&n);
	int x,y,z;
	for(int i=1;i<=n;i++){
		f[i]=i;
		scanf("%d%d%d",&x,&y,&z);
		e[i]=(E){x,y,z+1};
	}
	int ans=n;
	for(int i=n;i>=1;i--){
		sum[i]+=e[i].w;
		while(sum[i]>e[i].c){
			sum[find(ans)]-=e[ans].w;
			ans--;
		}
		int u=i,v=e[i].p;
		sum[v]+=sum[u];
		f[u]=v;
	}
	printf("%d\n",ans);
	return 0;
}