Codeforce101061E-Playing with nu

• Playing with numbers

• 题意：

• 给你两个数字s和n，在不改变s的数字顺序下，删除n个数使剩下来的数最大或最小。(包含前导零）。并且n不会大于s的长度。

• 思路：

• 给出数字s就一定知道数字s的长度len，len个数字删除n个数字，那么剩下X=len-n个数字。要使得这X个数字组成的数W最小。所以最高位首先应该最小。那首位的范围在哪呢？假如在全部的数字(1~len)中查找，那假如最后一个数字最小，组合的数字W的第二位肯定在第一位后面，那就不可行了，就找不到X个数字了。所以极端的思想就是找到len个数字最后的X个数字组合的数就是我们要求的最大数或最小数。那么第一个数字一定在(1~n+1)中出现。
• 我们可以这样来模拟一下：假设A数组就只有6个数，分别是A[1]，A[2]，A[3]，A[4]，A[5]，A[6]，我们去掉 n=2个数，使形成的值最小。
  那么我们此时的len=6,n=2，X=len-n=4
  则我们说形成的4位数的第一位一定在区间[1，3]中出现，因为如果区间范围再大点，比如[1，4]，这样就不科学了，因为第一位一定不会是A[4]，更不会是
  A[5]，A[6]，我们假设可以是A[4]，那么后面只有A[5]，A[6]两位数了，这样的话最多只可能形成3位数，绝对不能形成len-n=4位了。
  当然到了这里，我们就可以这样做了，第一位可以在区间[1，n+1]里面找，假设第一位在位置tem，因为第二位肯定在第一位的后面，所以第二位一定存在于
  区间[tem+1，n+2]，为什么是n+2,因为第一位已经确定了，现在只需要确定len-n-1位了，第二次继续采用极端的思想，len最后的几位符合情况，那么说明第二次的第一个数是n+2,搜索区间是[tem+1,n+2],所以区间就可以向后增加1，一直这样循环下去，就可以找到留下来的最大值或最小值。

#include<bits/stdc++.h>
using namespace std;
queue<char>qu1,qu2;
char s[100010];
int dpmaix[100010][24];//存放的是第i个字符开始，连续的2^j个字符的最大字符的下标
int dpminx[100010][24];//存放的是第i个字符开始，连续的2^j个字符的最小字符的下标
int n;
int findmaix(int x,int y)//返回较大字符的下标
{
    if(s[x]>=s[y])
    {
        return x;
    }
    else
    {
        return y;
    }
    
}
int findminx(int x,int y)//返回较小字符的下标
{
    if(s[x]<=s[y])
    {
        return x;
    }
    return y;
}
void ST(int n)
{
    for(int i=0;i<n;i++)
    {
        dpmaix[i][0]=dpminx[i][0]=i;//初始化(从第i个连续的1个字符中自身最大或最小)
    }
    for(int j=1;j<=25;j++)
    {
        for(int i=0;i+(1<<j)-1<n;i++)
        {
            dpmaix[i][j]=findmaix(dpmaix[i][j-1],dpmaix[i+(1<<(j-1))][j-1]);//寻找从第i个字符连续的2^j个字符中最大的字符下标
            dpminx[i][j]=findminx(dpminx[i][j-1],dpminx[i+(1<<(j-1))][j-1]);//寻找从第i个字符连续的2^j个字符中最小的字符下标
        }
    }
}
int querymaix(int i,int j)
{
    int k=log2(j-i+1.0);
    return findmaix(dpmaix[i][k],dpmaix[j-(1<<k)+1][k]);//返回区间的最大字符的下标
}
int queryminx(int i,int j)
{
    int k=log2(j-i+1.0);
    return findminx(dpminx[i][k],dpminx[j-(1<<k)+1][k]);//返回区间的最小字符的下标
}
int main( )
{
    int t;
    cin>>t;
    getchar( );
    while(t--)
    {
        while(!qu1.empty( ))
        {
            qu1.pop( );
        }
        while(!qu2.empty( ))
        {
            qu2.pop( );
        }
        scanf("%s %d",s,&n);
        //cout<<s<<endl;
        int len=strlen(s);
        ST(len);
        int x=len-n;
        int temaix=0,tep=n,teminx=0;
        for(int i=1;i<=x;i++)
        {
            temaix=querymaix(temaix,tep);
            teminx=queryminx(teminx,tep);
            tep++;//区间n往后移动
            qu1.push(s[temaix]);
            qu2.push(s[teminx]);
            temaix++;
            teminx++;
        }
        while(!qu2.empty( ))
        {
            cout<<qu2.front( );
            qu2.pop( );
        }
        cout<<endl;
        while(!qu1.empty( ))
        {
            cout<<qu1.front( );
            qu1.pop( );
        }
        cout<<endl;
    }
    return 0;
}