【贪心】Salaries

贪心

传送塔：CodeVS2587

POI2012，真是好题啊

思路：先预处理last[x]表示小于等于x的最大元素是多少 每个点能填的最大值即为其父亲能填的最大值减1，可以用宽搜搜出每个点能填的最大值 同时对于每个数k，处理出能填的最大值为k的点的个数 然后从小到大枚举数k，如果此时小于等于k的数中，只有k仍未被确定分配给哪个点， 且存在一个数能填的最大值为k，那么就把k分配给这个数。否则就把这个数压到一个黑箱里。 可以发现黑箱里的数可以用于填补不确定的点，并且可以互换。

代码虽短但内容很丰富：

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
38
39
40
41
42
43
44
45
46
47
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define N 3000000
int n,root,a[N],b[N],last[N],head[N],nxt[N],fa[N],q[N],pos[N],sum[N];
int getint(){
	char ch; int sum=0;
	for (ch=getchar();ch<'0' || ch>'9';ch=getchar());
	for (;ch>='0' && ch<='9';ch=getchar()) sum=sum*10+ch-'0';
	return sum;
}
void add(int x,int y){nxt[y]=head[x]; head[x]=y;}
int getlast(int x){return x==last[x]?x:getlast(last[x]);}
int main(){
	n=getint();
	for (int i=1;i<=n;i++) last[i]=i;//------last[x]记录未确定的小于x的最大元素
	for (int i=1;i<=n;i++){
		fa[i]=getint(); a[i]=getint();
		if (a[i]){b[i]=a[i]; last[a[i]]=a[i]-1;}
		if (fa[i]!=i) add(fa[i],i); else{root=i; fa[root]=0;}
	}
	
	int tt=0,ww=1; q[1]=root; a[0]=n+1;
	while (tt<ww){
		int u=q[++tt];
		if (!a[u]){a[u]=getlast(a[fa[u]]-1); pos[a[u]]=u; sum[a[u]]++;}
		for (int i=head[u];i;i=nxt[i]) q[++ww]=i;
	}
	
	int tmp=0;
	for (int i=1;i<=n;i++){//------------枚举每个权值 
		if (last[i]==i) tmp++;//----------黑箱中权值个数增加
		if (sum[i] && tmp==1) b[pos[i]]=i;//--------黑箱中权值唯一
		tmp-=sum[i];//-----------拿黑箱中的权值进行填补
	}
	
	for (int i=1;i<=n;i++) printf("%d\n",b[i]);
	
	return 0;
}