删数游戏
time limit per test 1 second memory limit per test 256 megabytes
Description
小明的老师近日在课堂上对全班同学提出了如下的删数问题供大家思考:任意给定一个有若干个数码组成的自然数n,,要求一个一个地在其中删除数字,共删除k个数,使得剩下的数码组成的数最小。小明回家后写了一些数进行试验,随后来到你处坚持要你帮他核对他删数所得的结果是否正确,你能帮他个忙吗?

传送门:SHUOJ2073

Input

输入的第1行是一个正整数T,表示下面有T行测试数据,(1<=T<=20)。接下来有T行,每行上有两个正整数n、k,但正整数n的有效位数len可达240位,k<len。

Output

对每组测试数据n、k,输出n被删除其中的k个数码后所的最小数字,该最小数字无多余的前导数码0。

Sample Input

1
2
3
2
178543 4
18541397 4

Sample Output

1
2
13
1137

题解

贪心,每次从前往后扫,对还没删的数,删除遇到的第一个非递减序列的最后一个元素 有几个坑,一是前置零要删去,而全零则输出零
## AC code:(不包含输入类)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
import java.io.*;  
import java.util.*;
import java.util.concurrent.LinkedBlockingQueue;
public class Main {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
PrintWriter pw=new PrintWriter(System.out);
int n=sc.nextInt();
for(int o=1;o<=n;o++){
String s=sc.next();
int k=sc.nextInt();
int slen=s.length();
boolean[]flag=new boolean[slen];
Arrays.fill(flag, true);
for(int i=1;i<=k;i++){
int index=0;
Queue<Node>queue=new LinkedBlockingQueue<Node>();
for(int j=0;j<s.length();j++){
if(flag[j]){
queue.add(new Node(s.charAt(j)-'0',j));
}
}
Node temp=queue.poll();
index=temp.index;
while(!queue.isEmpty()){
Node t=queue.poll();
if(t.i>=temp.i){
index=t.index;
temp=t;
}
else break;
}
flag[index]=false;
}
boolean start=false;
for(int i=0;i<slen;i++){
if(flag[i]){
if(s.charAt(i)-'0'!=0){
start=true;
}
if(start)
pw.print(s.charAt(i)-'0');
}
}
if(start==false) pw.print(0);
pw.println();

pw.flush();
}
}

}
class Node{
int i;
int index;
Node(int i,int index){
this.i=i;
this.index=index;
}
}