贪心+二分+逆序获取最小字典序输出

解题思路:首先得知道什么是最长递增子序列LIS，自行百度，一般有两种做法，一种是一维线性dp复杂度为n^2,另一种是贪心+二分，符合本题的要求。

1、很明显游客名单这是一个严格递增子序列，那就按规则建立字符串数组（很简单，怎么实现都行，也可以用substr()）

2、求LIS，遍历1-n,d[i]记录已经已经得到的LIS序列，比较a[i]与d的目前最末尾值（代码中为d[ans]），若a[i]更大，则ans++,a[i]直接加入到d。否则在d中找到第一个大于等于a[i]的数，并替换之。（这就是贪心的思想了，使得序列尽量小，这样序列更长，注意d中的序列并不是我们要求的序列的但它的长度等于我们要求序列的长度）

3、我们想得到LIS序列，光长度不行，数组len[i]记录以i结尾的LIS的长度，通过记录这个，就可以追溯LIS序列，

例如：

1 2 3 8 7 5  ;len:1 2 3 4 4 4 ;LIS: 1 2 3 5  ，其实就是逆序遍历，ans表示我们求得的LIS长度，在这里是4，先找到第一个len[i]为4的也就是5，然后找第一个len为3的值，依次递推。
注意事项:

参考代码:

#include using namespace std;
#define int long long 
const int N = 1e6 + 15;
int ans;
string s;
vector a;
string d[N];
int len[N];
signed main(){
	cin>>s;
	string t="";a.push_back(t);
	for(int i=0;i<s.size();i++){//以大写分割字符串 
		if(i==s.size()-1) {
			if(s[i]<='Z') {
				a.push_back(t);
				t=s[i];
				a.push_back(t); continue;
			}
			t+=s[i];
			a.push_back(t);
			continue;
		}
		if(s[i]<='Z'){
			if(t!="") a.push_back(t);
			t=s[i];
		}else{
			t+=s[i];
		}
	}
	
	//LIS
	d[1]=a[1];ans=1; len[1]=1;
	for(int i=2;i0){//若大于d中结尾值，直接加上去 
			ans++;d[ans]=a[i];
			len[i]=ans;
		}else{//d为升序，查找第一个大于等于a[i]的值进行替换 
			int l=1,r=ans;
			while(l>1;
				if((a[i].compare(d[mid])0)) l=mid+1;
				else {
					l=mid;break;
				}
			}
			int j=l; 
			d[j]=a[i];
			len[i]=j;//表明i结尾的LIS长度是j也就是l，即d中找到第一个大于等于a[i]的数的位置
		}
	}
	
	vector ve;
	for(int i=a.size()-1;i>=1;i--){//逆序查找
		if(ans=0;i--){
		cout<<ve[i];
	}			
	return 0;
}