练习题

题目意思：给你N个数，从中去掉K个数，能得到的最大的数是多少？

有T组测试数据，没组测试数据有N,K两个整数组成（1<=k<n<=500000）。

样例：

3

4 2

1 9 2 4

7 3

1231234

10 4

4177252841

输出：

94

3234

775841

分析题目：

用P来记录筛选的前一个数的位置，那么下一次筛选的位置范围是（p+1，i+k）。在这个范围找到最大的数。但是这样会超时，所以要优化找到做大的数。因为每一位数字的取值范围都是0-9，所以每次枚举从9-0，位置范围还是一样的。

代码：

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int MAXN = 500005;

char s[MAXN], a[MAXN];
vector< int > v[10];

int main( void )
{
// freopen( "d.in","r",stdin );
// freopen( "out.txt","w",stdout );

int n, k,t;
scanf("%d",&t);
while(t--)
{
for(int i=0;i<10;i++)
v[i].clear();

scanf( "%d %d", &n, &k );
scanf( "%s", s );

for( int i = n-1; i >= 0; --i )
v[ s[i]-'0' ].push_back( i );

int m = n-k, p = 0;
for( int i = 0; i < m; ++i ) { //biramo n-k znamenaka
for( int j = 9; j >= 0; --j ) {
while( v[j].size() > 0 && v[j].back() < p ) v[j].pop_back();
if( v[j].size() > 0 && n-v[j].back()-1 >= m-i-1 ) { p = v[j].back(); break; }
}
a[i] = s[p], p++;
}

a[m] = '\0';
puts( a );
}
return 0;
}