-
-
题意：
- 给你两个数字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;
}
网友评论