题目链接
题意
给你一个字符串，要你构造一个长为(k)的子串使得每个字母出现的次数在([L_i,R_i](0leq ileq26))间且字典序最小。
思路
做这种题目就是要保持思路清晰，博主就是因为写的时候没有想清楚写了一晚上(+)一个早上……
首先我们对于第(i)个位置有如果这个位置可以摆放，那么(L[s[i]-'a'],R[s[i]-'a'],k)均减少(1)，如果不能摆放(条件为：(sumlimits_{i=0}^{26}L[i]leq tot-1,L[i]>0))那么就(continue)。
至于字典序最小，我们对于每个可以摆放的位置用单调栈来维护即可。
代码实现如下
#include <set>
#include <map>
#include <deque>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <bitset>
#include <cstdio>
#include <string>
#include <vector>
#include <cassert>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
typedef pair<LL, LL> pLL;
typedef pair<LL, int> pLi;
typedef pair<int, LL> pil;;
typedef pair<int, int> pii;
typedef unsigned long long uLL;
#define lson rt<<1
#define rson rt<<1|1
#define lowbit(x) x&(-x)
#define name2str(name) (#name)
#define bug printf("*********
")
#define debug(x) cout<<#x"=["<<x<<"]" <<endl
#define FIN freopen("in.txt","r",stdin)
#define IO ios::sync_with_stdio(false),cin.tie(0)
const double eps = 1e-8;
const int mod = 1000000007;
const int maxn = 100000 + 7;
const double pi = acos(-1);
const int inf = 0x3f3f3f3f;
const LL INF = 0x3f3f3f3f3f3f3f3fLL;
int tot;
char s[maxn];
stack<int> st;
vector<char> vec;
int L[30], R[30], sum[maxn][30];
int main() {
while(~scanf("%s%d", s, &tot)) {
int n = strlen(s);
for(int i = 0; i < 26; ++i) sum[n][i] = 0;
for(int i = 0; i < 26; ++i) {
scanf("%d%d", &L[i], &R[i]);
}
for(int i = n - 1; i >= 0; --i) {
for(int j = 0; j < 26; ++j) {
sum[i][j] = sum[i+1][j];
}
int x = s[i] - 'a';
++sum[i][x];
}
while(!st.empty()) st.pop();
for(int i = 0; i < n; ++i) {
int x = s[i] - 'a', cnt = 0;
if(R[x] == 0) continue;
--L[x], --R[x];
for(int j = 0; j < 26; ++j) {
if(L[j] > 0) cnt += L[j];
}
if(tot > 0 && cnt > tot - 1) {
++L[x], ++R[x];
continue;
}
if(tot > 0) {
while(!st.empty() && s[i] < s[st.top()]) {
int tmp = s[st.top()] - 'a';
if(L[tmp] + 1 > sum[i+1][tmp]) break;
++L[tmp], ++R[tmp];
st.pop();
++tot;
}
--tot;
st.push(i);
} else if(tot == 0) {
while(!st.empty() && s[i] < s[st.top()]) {
int tmp = s[st.top()] - 'a';
if(L[tmp] + 1 > 0) break;
++L[tmp], ++R[tmp];
st.pop();
++tot;
}
if(tot > 0) {
--tot;
st.push(i);
} else {
++L[x], ++R[x];
}
} else {
++L[x], ++R[x];
}
}
int flag = 1;
for(int i = 0; i < 26; ++i) {
if(L[i] > 0) {
flag = 0;
break;
}
}
if(!flag || tot > 0) {
printf("-1
");
continue;
}
vec.clear();
while(!st.empty()) {
vec.push_back(s[st.top()]);
st.pop();
}
for(int i = (int)vec.size() - 1; i >= 0; --i) {
printf("%c", vec[i]);
}
printf("
");
}
return 0;
}