sol

首先可以把依赖关系转成一个森林。自下而上维护出每个点的\(size\)，表示这关解锁以后一共有多少关。

考虑没有重复数字的情况。

直接从小往大贪心把每个数赋给当前已解锁的最后一关就可以了。

有重复？

一样的。重复的数字一起考虑，假设有\(k\)个重复的数，那就把这个数先赋给第\(k\)大的位置，然后是\(k-1\)大。。。直到\(k\)个数全部填满。

code

#include<cstdio>

#include<algorithm>

#include<cmath>

using namespace std;

int gi()

{

	int x=0,w=1;char ch=getchar();

	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();

	if (ch=='-') w=0,ch=getchar();

	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();

	return w?x:-x;

}

const int N = 5e5+5;

int n,d[N],nxt[N],head[N],fa[N],sz[N],t[N<<2],ans[N];

double k;

void dfs(int u)

{

	sz[u]=1;

	for (int v=head[u];v;v=nxt[v])

		dfs(v),sz[u]+=sz[v];

}

void modify(int x,int l,int r,int p,int v)

{

	t[x]+=v;if (l==r) return;

	int mid=l+r>>1;

	if (p<=mid) modify(x<<1,l,mid,p,v);

	else modify(x<<1|1,mid+1,r,p,v);

}

int query(int x,int l,int r,int k)

{

	if (l==r) return l;int mid=l+r>>1;

	if (k<=t[x<<1|1]) return query(x<<1|1,mid+1,r,k);

	else return query(x<<1,l,mid,k-t[x<<1|1]);

}

int main()

{

	n=gi();scanf("%lf",&k);

	for (int i=1;i<=n;++i)

	{

		fa[i]=(int)floor(i/k);

		if (fa[i]) nxt[i]=head[fa[i]],head[fa[i]]=i;

	}

	for (int i=1;i<=n&&!fa[i];++i) dfs(i);

	for (int i=1;i<=n&&!fa[i];++i) modify(1,1,n,i,sz[i]);

	for (int i=1;i<=n;++i) d[i]=gi();sort(d+1,d+n+1);

	for (int i=1,j=1;i<=n;i=j)

	{

		while (j<=n&&d[j]==d[i]) ++j;

		for (int k=j-i;k;--k)

		{

			int u=query(1,1,n,k);ans[u]=d[i];

			modify(1,1,n,u,-sz[u]);

			for (int v=head[u];v;v=nxt[v]) modify(1,1,n,v,sz[v]);

		}

	}

	for (int i=1;i<=n;++i) printf("%d ",ans[i]);

	puts("");return 0;

}

巴特西

[BZOJ5249][多省联测2018]IIIDX

sol

code

最新文章

热门文章