题意:

给你一个长度不超过 长度的只包含小写字母的字符串s，和一个整数k，要你求出长度为k的s的字典序最小子序列。

且给你两个长度为26的L数组, R数组作为限制条件， L[0] 表示 字符 'a' 在 子序列中的最少个数，  R[0] 表示 字符 'a' 在 子序列中的最多个数，依次类推。

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=6586

题解：

先构造出某个位置后每个字母的个数，用一个动态数组存每个字母的各个位置。

一位位地构造答案字符串，每次贪心地加能加入的最小的字符 (判断能否加入只要判断加入之后原字符串剩下的后缀中的每种字符的数目能否足够满足条件)

AC_code:

#include<bits/stdc++.h>
#define maxn 100005
using namespace std;

char s[maxn], s1[maxn];
int k, n, l[26], r[26];
int cnt[maxn][26]; // 当前字符的后面的字符中所包含的每种字符的数量
int used[26];//当前已用的每个字符的数量
vector<int> g[26];
int main() {
	while(~scanf("%s%d", s, &k)) {
		memset(used, 0, sizeof(used));
		for(int i = 0; i < 26; i++) {
			scanf("%d %d", &l[i], &r[i]);
		}
		n = strlen(s);
		for(int i = 0; i < 26; i++) {
			cnt[n][i] = 0;
			g[i].clear();
		}
		for(int i = n-1; i >= 0; i--) {
			for(int j = 0; j < 26; j++) {
				cnt[i][j] = cnt[i+1][j] + (s[i] == ('a' + j));
			}
		}
		for(int i = 0; i < n; i++) {
			g[s[i] - 'a'].push_back(i);//每种字符的位置
		}
		vector<int>::iterator head[26];//指向vector<int>容器中的元素的迭带器对象
		for(int i = 0; i < 26; i++){
			head[i] = g[i].begin();
		}
		/*   head[i] 表示可以取的最前面的  'a'+i  的位置*/
		int last = -1;
		bool ff = 0;
		for(int i = 0; i < k; i++) {
			bool f = 0;
			for(int j = 0; j < 26; j++) {
				if(used[j] == r[j]) {
					continue;
				}
				while(head[j] != g[j].end() && (*head[j]) <= last) { //还有字符且可以没超出限制
					head[j]++;
				}
				if(head[j] == g[j].end()) { //没有字符
					continue;
				}
				used[j]++;
				bool flag = 1;
				int pos= *head[j], sum = 0;
				for(int t = 0; t < 26; t++) {
					if(cnt[pos + 1][t] + used[t] < l[t]) {
						flag = 0; //后面的字符无法满足最少的要求
					}
					sum += max(l[t] - used[t], 0);// 后面至少我们还需要加的字符数量
				}
				if(sum > k - i - 1) { //剩余的空间无法满足还需要加的字符数量
					flag = 0;
				}
				sum = 0;
				for(int t = 0; t < 26; t++) {
					sum += min(cnt[pos + 1][t], r[t] - used[t]);// 最多还能加的字符的数量
				}
				if(sum < k - i - 1) { //还能加的字符数量填不满剩余的空间
					flag = 0;
				}
				if(flag == 0) { //当前字符不可取 j
					used[j]--;//当前字符不装进去
				} else {
					s1[i] = 'a' + j;
					f = 1;
					last = pos;//原字符串的取得最后一个位置更新
					break;
				}
			}
			if(f == 0) {
				puts("-1");
				ff = 1;
				break;
			}
		}
		if(ff == 0) {
			s1[k] = 0;
			printf("%s\n", s1);
		}
	}
	return 0;
}