A Broken Calculator 最详细的解题报告

题目如下（链接有可能无法访问）：

A Broken Calculator

Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

Problem

Dave's calculator is broken. His calculator halts when put more than K kinds of number.

Dave wants to input an integer A, but if he put this number correctly the calculator might halt. Instead, he inputs the closest integer that won't halts the calculator.

Output the difference between Dave's input and the integer A.

Input

The input will be given in the following format from the Standard Input.

A K

On the first line, you will be given the integer A(1≦A≦1015), the integer Dave wants to input, followed by a space andK(1≦K≦10), the kinds of number his calculator can recognize.

Acheivements and Points

When you pass every test case where 1≦A≦100,000, you will be awarded 30 points.
In addition, if you pass all the rest test cases you will be awarded 70 more points.

Output

Output the minimum difference between Dave's input and the integer A in one line. Make sure to insert a line break at the end of the output.

Input Example 1

1234 2

Output Examle 1

In this case Dave can only use up to 2 kinds of numbers.

He will input the closest integer 1222, so the difference is 12.

Input Example 2

800000 1

Output Example 2

22223

Dave can use only 1 number, so 777777 is the closest integer.

Inout Example 3

7328495 10

Output Example 3

In this case Dave's calculator is not broken at all.

He can input the given integer A as is.

Input Example 4

262004 2

Output Example 4

218

The closest integer is 262222.

解题思路：

设A的数字长度为L，首先寻找K个数，对剩余的L-K数分别计算最大值和最小值，在计算的时候要考虑借位和进位的情况。

具体算法（java版，直接AC）

  1 import java.math.BigInteger;
  2 import java.util.Arrays;
  3 import java.util.Scanner;
  4 
  5 public class Main{
  6     
  7     public int[]available;
  8     public String target;
  9     public int limited;
 10     
 11     public Main(String target,int limited){
 12         this.available=new int[10];
 13         this.target=target;
 14         this.limited=limited;
 15     }
 16     private int getIntByIndex(int index){
 17         return this.target.charAt(index)-'0';
 18     }
 19     
 20     private BigInteger substract(String str1,String str2){
 21         BigInteger a=new BigInteger(str1);
 22         BigInteger b=new BigInteger(str2);
 23         if(a.compareTo(b)>0){
 24             return a.subtract(b);
 25         }else{
 26             return b.subtract(a);
 27         }
 28     }
 29     private String convertTo(int[]array){
 30         StringBuffer buffer=new StringBuffer();
 31         for(int i=0;i<array.length;i++){
 32             buffer.append(array[i]);
 33         }
 34         return buffer.toString();
 35     }
 36     
 37     public void solve(){
 38         int index=0;
 39         int k=this.limited;
 40         for(;index<this.target.length();index++){            
 41             int j=this.getIntByIndex(index);
 42             if(this.available[j]==0){
 43                 if(k==0){
 44                     break;
 45                 }
 46                 this.available[j]=1;
 47                 k--;
 48             }            
 49         }
 50         if(index==this.target.length()){
 51             System.out.println("0");
 52             return;
 53         }
 54         int[]copy=Arrays.copyOf(this.available, this.available.length);
 55         BigInteger diff1=this.substract(this.convertTo(this.calculateMax(copy, index)), this.target);
 56         BigInteger diff2=this.substract(this.target,this.convertTo(this.calculateMin(this.available, index)));
 57         if(diff1.compareTo(diff2)>0){
 58             System.out.println(diff2.toString());
 59         }else{
 60             System.out.println(diff1.toString());
 61         }
 62     }
 63     
 64     private int getValue(int[] avail,boolean less){
 65         if(less){
 66             for(int i=0;i<=9;i++){
 67                 if(avail[i]>0)
 68                     return i;
 69             }
 70         }else{
 71             for(int i=9;i>=0;i--){
 72                 if(avail[i]>0)
 73                     return i;
 74             }
 75         }
 76         return -1;
 77     }
 78     
 79     public int[] calculateMax(int[] avail,int index){
 80         int[]result=new int[this.target.length()];
 81         int nextValue=Integer.MIN_VALUE;
 82         for(int i=0;i<index;i++){
 83             result[i]=this.getIntByIndex(i);
 84         }
 85         for(int i=0;i<=9;i++){
 86             if(avail[i]>0&&i>this.getIntByIndex(index)){
 87                 nextValue=i;
 88                 break;
 89             }
 90         }
 91         if(nextValue==Integer.MIN_VALUE){
 92             nextValue=this.getIntByIndex(index-1)+1;
 93             for(int j=index-1;j>=0;j--){
 94                 if(result[j]==nextValue-1){
 95                     result[j]=nextValue;
 96                 }
 97             }
 98             result[index-1]=nextValue;
 99             avail[nextValue-1]=0;
100             int min=Integer.MAX_VALUE;
101             if(avail[nextValue]==0){
102                 avail[nextValue]=1;
103                 min=this.getValue(avail, true);
104             }
105             for(int j=index;j<this.target.length();j++){
106                 result[j]=min;
107             }
108         }else{
109             result[index] = nextValue;
110             int min=this.getValue(avail, true);
111             for(int i = index + 1; i < result.length; i++)
112             {
113                 result[i] = min;
114             }
115         }
116         return result;
117     }
118     
119     public int[] calculateMin(int[] avail,int index){
120         int[]result=new int[this.target.length()];
121         int nextValue=Integer.MIN_VALUE;
122         for(int i=0;i<index;i++){
123             result[i]=this.getIntByIndex(i);
124         }
125         for(int i=9;i>=0;i--){
126             if(avail[i]>0&&i<this.getIntByIndex(index)){
127                 nextValue=i;
128                 break;
129             }
130         }
131         if(nextValue==Integer.MIN_VALUE){
132             if(index==1&&this.getIntByIndex(0)==1){
133                 result=new int[this.target.length()-1];
134                 for(int j=0;j<result.length;j++){
135                     result[j]=9;
136                 }
137             }else{
138                 nextValue=this.getIntByIndex(index-1)-1;
139                 for(int j=index-1;j>=0;j--){
140                     if(result[j]==nextValue+1){
141                         result[j]=nextValue;
142                     }
143                 }
144                 result[index-1]=nextValue;
145                 avail[nextValue+1]=0;
146                 int max=Integer.MIN_VALUE;
147                 if(avail[nextValue]==0){
148                     avail[nextValue]=1;
149                     max=this.getValue(avail, false);
150                 }
151                 for(int j=index;j<this.target.length();j++){
152                     result[j]=max;
153                 }
154             }
155         }else{
156             result[index] = nextValue;
157             int max=this.getValue(avail, false);
158             for(int i = index + 1; i < result.length; i++)
159             {
160                 result[i] = max;
161             }
162         }
163         return result;
164     }
165     
166     public static void main(String[] args) {
167         Scanner scanner=new Scanner(System.in);
168         Main m=new Main(scanner.next(),scanner.nextInt());
169         m.solve();
170     }
171 }