首页 > 代码库 > A Broken Calculator 最详细的解题报告
A Broken Calculator 最详细的解题报告
题目来源：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
12
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
0
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=http://www.mamicode.com/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=http://www.mamicode.com/i; 88 break; 89 } 90 } 91 if(nextValue=http://www.mamicode.com/=Integer.MIN_VALUE){ 92 nextValue=http://www.mamicode.com/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=http://www.mamicode.com/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=http://www.mamicode.com/i;128 break;129 }130 }131 if(nextValue=http://www.mamicode.com/=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=http://www.mamicode.com/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 }
A Broken Calculator 最详细的解题报告
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。