比赛 假期找点事儿做题吧 评测结果 AAAAAAAAAA
题目名称 上升序列 最终得分 100
用户昵称 CSU_Turkey 运行时间 1.083 s
代码语言 C++ 内存使用 0.47 MiB
提交时间 2017-06-09 20:44:50
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
int n,m,a[10008],b[10008],g[10008],h[10008],mid,book;
inline int erfen(int x,int y,int z)
{
	while(x<y)
	{
		int mid=(x+y)/2;
		if(b[mid]<=z)y=mid;
		else x=mid+1;
	}
	return x;
}
int main()
{
//	freopen("1.txt","r",stdin);
	freopen("lis.in","r",stdin);
//	freopen("b.out","w",stdout);
	freopen("lis.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	scanf("%d",&a[i]);
	scanf("%d",&m);
	memset(b,0x7f,sizeof(b));
		int len=1;
		for(int i=n;i>=1;i--)//这里一定要是倒着枚举,因为为了满足字典序,最后输出时需要从左往右来看
		//如果正枚举,得到的g数组无法看到后面是否有数字能满足以当前序列走可以满足题意 
		{
			int u=b[len-1];
			if(a[i]<u)
			b[len++]=a[i],
			g[i]=len-1;
			else
			{
				int ghb=erfen(1,len-1,a[i]);
				b[ghb]=a[i],
				g[i]=ghb;
			}
			/*if(len==x+1)
			{
				book=1;
				break;
			}*/
		}
		/*if(book==1)
		for(int i=len-1;i>=1;i--)
		cout<<b[i];
		else cout<<"Impossible";*/
	for(int j=1;j<=m;j++)
	{
		int x;
		scanf("%d",&x);
//		if(j!=206)continue;
		memset(h,0,sizeof(h));
		if(len-1<x)
		{
			cout<<"Impossible";
		}
		else 
		{
		//	for(int i=1;i<=n;i++)
		//	cout<<g[i]<<" ";
			int last=-100;
			int jj=1;
			for(int i=1;x;i++)
			{
				if(g[i]>=x&&a[i]>last) 
				{
					last=a[i];
					x--;
					h[jj++]=a[i];
				}//cout<<i<<" ";
			}
			for(int i=1;i<jj;i++)
			cout<<h[i]<<" ";
		}
	}
	return 0;
}