String（HDU-6586）

Problem Description

Tom has a string containing only lowercase letters. He wants to choose a subsequence of the string whose length is k and lexicographical order is the smallest. It's simple and he solved it with ease.

But Jerry, who likes to play with Tom, tells him that if he is able to find a lexicographically smallest subsequence satisfying following 26 constraints, he will not cause Tom trouble any more.

The constraints are: the number of occurrences of the ith letter from a to z (indexed from 1 to 26) must in [Li,Ri].

Tom gets dizzy, so he asks you for help.

Input

The input contains multiple test cases. Process until the end of file.

Each test case starts with a single line containing a string S(|S|≤105)and an integer k(1≤k≤|S|).

Then 26 lines follow, each line two numbers Li,Ri(0≤Li≤Ri≤|S|). 

It's guaranteed that S consists of only lowercase letters, and ∑|S|≤3×105.

Output

Output the answer string.

If it doesn't exist, output −1.

Sample Input

aaabbb 3

0 3

2 3

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

0 0

Sample Output

abb

题意：给出一个字符串与一个数 k，然后给出 26 行代表每个字母的个数限制 [li,ri]，要求构造一个字典序最小的、长度为 k 的满足限制条件的子序列，没有输出 -1

思路：

首先建立一个大小为 26 的队列数组，存放 26 个字母的各自位置

然后利用队列，在 k 个位置上贪心的按字典序逐个放字母，直到满足限制条件：

• 对于每个字母，其后的个数加上当前选的个数要大于等于 l[i]
• 对于每个字母，其后的个数取最小之后的和小于等于 k
• 对于每个字母，其后的个数取最大之后的和大于等于 k

Source Program

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#include<utility>
#include<stack>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<unordered_map>
#include<bitset>
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
#define Pair pair<int,int>
LL quickPow(LL a,LL b){ LL res=1; while(b){if(b&1)res*=a; a*=a; b>>=1;} return res; }
LL quickModPow(LL a,LL b,LL mod){ LL res=1; a=a%mod; while(b){if(b&1)res=(a*res)%mod; a=(a*a)%mod; b>>=1;} return res; }
LL getInv(LL a,LL mod){ return quickModPow(a,mod-2,mod); }
LL GCD(LL x,LL y){ return !y?x:GCD(y,x%y); }
LL LCM(LL x,LL y){ return x/GCD(x,y)*y; }
const double EPS = 1E-10;
const int MOD = 998244353;
const int N = 1000000+5;
const int dx[] = {-1,1,0,0,1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;

char str[N],res[N];
int l[N],r[N],num[N];
int sum[N][27];
int main() {
    int k;
    while(scanf("%s%d",str+1,&k)!=EOF) {
        memset(sum,0,sizeof(sum));
        memset(num,0,sizeof(num));
        int len=strlen(str+1);
        for(int i=len; i>=1; i--) {
            for(int j=0; j<26; j++) {
                if(str[i]=='a'+j)
                    sum[i][j]=sum[i+1][j]+1;
                else
                    sum[i][j]=sum[i+1][j];
            }
        }

        queue<int> Q[27];
        for(int i=0; i<26; i++)
            scanf("%d%d",&l[i],&r[i]);
        for(int i=1; i<=len; i++)
            Q[str[i]-'a'].push(i);

        int now=0;
        int tot=0;
        for (int i=1; i<=k; i++) {
            for (int j=0; j<26; j++) {
                if(num[j]==r[j])//不能大于最大限制
                    continue;
                while(!Q[j].empty()&&now>=Q[j].front())
                    Q[j].pop();
                if(!Q[j].empty()) {
                    bool flag=false;
                    int pos=Q[j].front();
                    num[j]++;//先放再判断

                    for(int p=0; p<26; p++) {
                        if(num[p]+sum[pos+1][p]>=l[p])//每个字母其后的个数加上当前选的个数要大于等于l[i]
                            continue;
                        else { //不满足
                            num[j]--;//拿走
                            flag=true;
                            break;
                        }
                    }
                    if(flag)
                        continue;

                    int minn=0,maxx=0;
                    for(int p=0; p<26; p++) {
                        minn+=max(l[p]-num[p],0);
                        maxx+=min(r[p]-num[p],sum[pos+1][p]);
                    }
                    if(minn+i<=k) { //每个字母其后的个数取最小之后的和小于等于k
                        if(maxx+i>=k){//每个字母其后的个数取最大之后的和大于等于k
                            res[tot++]=('a'+j);
                            now=Q[j].front();
                            break;
                        }
                    } else //不满足
                        num[j]--;//拿走
                }
            }
            if(tot!=i)
                break;
        }

        if(tot==k) {
            res[k]='\0';
            printf("%s\n",res);
        } else
            printf("-1\n");
    }
    return 0;
}