从一个n位数中选出m位按顺序组成新数并使其最大 || Erasing and Winning UVA

就是从n位数中取出n-d个数字按顺序排成一排组成一个新数使得其最大

算法：

从前往后确定每一位。找第i位时，要求后面留下d-i位的空间，

因此第i位应该从第i-1位原来位置+1到第d+i位寻找

用线段树确定区间最大值(其实直接用优先队列就行了，可能会多一些多余的出队操作)

更好的算法：

***引用

后来看到一个博客写的特别巧妙，

每读取一个字符，如果ans中有字符，且如果删除一个字符后面的数字数量依然够的话，

并且ans中最后一个数字比新读取的小，那么删除最后一个字符，把新读取的字符加入ans.

http://www.cnblogs.com/jihe/p/4883573.html***

#include<cstdio>

#include<algorithm>

using namespace std;

int c[300010];

int ans[300010];

int n,d;

struct Node

{

	int lc,rc,l,r,maxpos;

}node[1000010];

int num_node;

int getnode()

{

	return num_node++;

}

int build(int l,int r)

{

	int _tmp=getnode();

	node[_tmp].l=l;

	node[_tmp].r=r;

	if(l==r)

	{

		node[_tmp].maxpos=l;

		return _tmp;

	}

	int m=(l+r)>>1;

	node[_tmp].lc=build(l,m);

	node[_tmp].rc=build(m+1,r);

	if(c[node[node[_tmp].lc].maxpos]<c[node[node[_tmp].rc].maxpos])

		node[_tmp].maxpos=node[node[_tmp].rc].maxpos;

	else

		node[_tmp].maxpos=node[node[_tmp].lc].maxpos;

	return _tmp;

}

int query(int L,int R,int nownode)

{

	int l=node[nownode].l;

	int r=node[nownode].r;

	if(L<=l&&r<=R)

		return node[nownode].maxpos;

	int t,ans=n+1,m=(l+r)>>1;

	if(L<=m)

	{

		t=query(L,R,node[nownode].lc);

		if(c[ans]<c[t])

			ans=t;

	}

	if(R>m)

	{

		t=query(L,R,node[nownode].rc);

		if(c[ans]<c[t])

			ans=t;

	}

	return ans;

}

int main()

{

	int i,t;

	scanf("%d%d",&n,&d);

	while(n!=0&&d!=0)

	{

		num_node=0;

		t=0;

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

			scanf("%1d",&c[i]);

		c[n+1]=-1;

		build(1,n);

		for(i=1;i<=n-d;i++)

		{

			t=query(t+1,d+i,0);

			printf("%d",c[t]);

		}

		printf("\n");

		scanf("%d%d",&n,&d);

	}

	return 0;

}

巴特西

从一个n位数中选出m位按顺序组成新数并使其最大 || Erasing and Winning UVA - 11491

最新文章

热门文章