原题:
有一个数字的集合A和一个整数M,找到一个由A中数字组成,且比M大的最小整数。
例如A = {0, 1} M = 21,ANSWER = 100
题解:
最常规思路,从当前的数字开始一个一个遍历下去,判断该数值是否只用了规定的数字。要被打脸的即视感,PASS。
好吧,再想一想的话,应该最好的办法就是把解构造出来,字典序模拟加法。
首先我们举一个例子:
A={2, 5, 7} M = 258916973。很显然答案是272222222,怎么得到这个答案的呢?(看到后面一排2了没有)
首先,我们要从M的最高位开始入手。对于A中不存在的数字,我们为了使答案符合由A中的数字组成这一条件,我们必须将这一位的数字变大。也就指的是M的第三位,所以我们将M拆成两部分也就是25(8+) 916973。那么由于前三位很明显会变大,所以我们这后面的六位可以贪心的全部填上最小的数字,然后就变成了25(8+) 222222。然后再来处理前面的部分,前面就完全类似普通的加法了,8变成了最小的2然后进位,然后5变成了7结束进位。然后就是结果了272222222。当然在处理前面的这些的时候,我们要考虑一下特殊情况,就是最高位要进位,这个时候首位是A中非0的最小数字哟。
当A中包括了所有的数字时,这个时候算法就退化成了模拟加法了。也就是这个算法的后一部分。
贴上源代码:
/* * LwwGame.c * * Created on: 2013-11-3 * Author: root */ #include <stdlib.h> #include <stdio.h> #include <string.h> static int T = 3; static char A[10]="257", buf[128]="257984651"; inline void swap( char *a, char *b ) { char c = *a; *a = *b; *b = c; } void reverse() { int i, j; for(i=0, j=strlen(buf)-1; i<j; i++, j--) swap(&buf[i], &buf[j]); } int exist(char c) { int i; for(i=0; i<T; i++) if(A[i]==c) return 1; return 0; } void regularization() { int flag, i, j=0; reverse(); for(flag=strlen(buf)-1; flag>0; flag--) if(!exist(buf[flag])) break; for(i=0; i<flag; i++) buf[i] = A[0]; for(i=flag; buf[i]!='\0'; i++) { for(j=0; A[j]!='\0'; j++) if(A[j]>buf[i]) break; buf[i] = (A[j]=='\0' ? A[0] : A[j]); if(A[j]!='\0') break; } if(buf[i]=='\0') { buf[i] = A[0]=='0' ? A[1] : A[0]; buf[i+1] = '\0'; } reverse(); } int main() { int i, j; //scanf("%s", A); //scanf("%s", buf); T = strlen(A); for(i=0; i<T; i++) for(j=T-1; j>i; j--) if(A[j] < A[j-1]) swap(&A[j], &A[j-1]); regularization(); printf("%s\n", buf); return 0; }