C. C. Blog

Security Research, Algorithm and Data Structure

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#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;
}
  • 本文作者: CCWUCMCTS
  • 本文链接: https://ccwucmcts.github.io/posts/872/
  • 版权声明: 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!