题目：
给定正整数 k 和  n 位正整数 a (0 <= k <= n)。
从 a 中删掉任意 k 位数字，将剩下的给位数字按原次序排列组成一个新的正整数。
对于给定的 n 位正整数 a 和正整数 k，编程计算从 a 中删去 k 位数字后能够得到的最小的数。

[例]
输入： 5412873 3
输出： 1273

请大家贴出自己的思考也好，分析也好，算法也好，代码也好，多多交流，共同进步。
以下是我的思路和实现：

/*

 分析:

 以 a[i], (0 <= i < n)表示 n 位正整数 a 的第 i 位, a[0] 为最高位, a[n - 1] 为最低位, n 位数字 a 可以写成以下形式:

 a[0] * 10 ^ (n - 1) + a[1] * 10 ^ (n - 2) + a[2] * 10 ^ (n - 3) + ... + a[n - 2] * 10 ^ 1 + a[n - 1] * 10 ^ 0

 经观察可知 d[0] 比 d[k], (0 < k < n) 对数字 a 的值的影响比 d[k] 更为明显, 我们说 d[0] 比 d[k] 更为重要.

 一般而论, d[i] 比 d[k], (i < k < n) 更为重要.

 

 题目要求“剩下的数字按原次序排列组成一个新的正整数”和“对于给定的正整数 a,编程计算删去 k 个数字后得到的最小数”.

 因此思考的重点为如何得到最小的数.

 

 设 n - k = m, 题目的正确答案为 m 位数字 b,

 则 b[0] 必然是 a[0] ~ a[k] 中的一位数字, 且 b[0] 为 a[0] ~ a[k] 中 最小的一位数字, 如下例:

 

 n = 4, a = 4123, k = 2;

 从 4 位正整数 a 中删掉任意 2 位后,可能的结果为:

 12

 13

 23

 41

 42

 43

 b = 12, b[0] = 1 = a[2] 为 a[0] ~ a[2] (即 4, 1, 2) 中最小的数字.

 

 因此我们所设计的程序应首先找出a[0] ~ a[k] 中最小的一位 a[j], 并将此位作为答案的最高位 b[0]. 

 要达到此目的,必须从 n 为正整数 a 中删除 a[0] ~ a[j - 1] 共 j 位.

 因 a[j] 需要保留作为答案 b 的最高位,因此应将 j 从剩下的需要继续删除的数字中排除.

 

 至此我们已经从 n 位正整数 a 中删除了 j 位,并排除了 1 位,接下来我们还需要删除 k - j 位.

 为了保证最后的答案 b 最小, 必须保证从剩下的 n - j 位中删除 k - j位后所得的数字最小,为此我们只需要重复上述过程, 直至一共删除 k 位为止.

 

 算法: 

 1. s = 0; s 表示搜索的起始位置

 2. 找出 a[j] == min(a[s], a[s + 1], ... , a[k])

 3. a[0] = -1, a[1] = -1 ... a[j - 1] = -1; a[0] = -1 表示删除a[0];

 4. s = j + 1, k -= j - s; 从 a[j] 的下一位开始进行下一次的搜索, 即将 a[j] 从待删除数字中排除

 5. 重复 2 ~ 4, 直至 k == 0 || n - s == k; n - s == k 时不需要再进行搜索, 只要把 a[s] ~ a[n] 全部删掉即可

 

 代码:

 */


 #include <stdio.h>
#include <string.h>

 
int main() {
    char a[100] = {0}, i, j = 0, n, s = 0, is_1st_digit = 1;
    int k;
            
    printf("Please input number a: ");
    scanf("%s", a);
    n = strlen(a);
    printf("Please tell me how many digits to be deleted: ");
    scanf("%d", &k);
                                
    while (k > 0 && k < n - s) {
        // find the minimun digit a[j]
        for (i = s; i <= s + k; i++) {
            if (a[i] < a[j]) {
                if (!is_1st_digit || a[i] != '0') {
                    j = i;
                }
            }
        }

        // delet digits a[s] ~ a[j - 1]
        for (i = s; i < j; i++) {
            a[i] = -1;
        }
        
        // calculate how many more digits need to be deleted 
        k -= j - s;
        
        // next search will start from a[j + 1]
        j++;
        s = j;

        // there is only one 1st digit and we've already found it, so
        is_1st_digit = 0;
    }
    
    if (k > 0) {
        // delete digits d[s] ~ d[n]
        n = s;
    }
    
    // printf() the answer.
    for (i = 0; i < n; i++) {
        if (a[i] != -1) {
            printf("%c", a[i]);
        }
    }
    printf("\n");
    return 0;
}

[ 本帖最后由 voidx 于 2011-4-18 14:04 编辑 ]

让我想想！

找到最小的一个数字，然后在其后面找到小的n-k-1位数就可以了！

#include <stdio.h>
#include <string.h>
int main()
{
    char s[20] ;
    int n , m , len , i , j , ok ;
    while( ~scanf("%s", s ) )
    {
        ok = m = 0 ;
        len = (int)strlen( s ) ;
        scanf("%d", &n ) ;
        if( n >= len ) printf("0\n") ;
        else
        {
            for( i = 1 ; i < len && !ok ; ++i )
            {
                for( j = i -1 ; j >= 0 && !ok ; --j )
                {
                    if( s[j] >= s[i] )
                        s[j] = '0' , m++ ;
                    if( m == n )
                        ok = 1 ;
                }
            }
            i = n - m ;
            while( i )
                s[len-i] = '0' , i-- ;
            for( i = 0 ; i < len ; ++i )
            {
                if( s[i] != '0' )
                    putchar(s[i]) ;
            }
            printf("\n") ;
        }
    }
    return 0 ;
}

3楼的解法有误， 5412873 1

[ 本帖最后由 『点点滴滴』 于 2011-4-18 08:24 编辑 ]

例如 5412873 3

先遍历 5412873，得到tmp[10];
0: 0个
1: 1个
2: 1个
3: 1个
4: 1个
5: 1个
6: 0个
7: 1个
8: 1个
9: 0个

再遍历tmp[10]，得到 5（大于5的数一定要删）和1（对于5，需要删除掉一个）
最后遍历 5412873，删除大于等于5的数，删除1个等于5的数。

-----------------------

再例如 1477902 2
得到 7, 1
得到 14702

我说错了，没看清题目要求，要求是最小数


[ 本帖最后由 rjsp 于 2011-4-18 11:08 编辑 ]

确实挺难！！！

请在代码中适当的加一点注释，方便大家阅读

不知道这种算法对不对？代码用MinGW 4.5编译通过（-std=c99）

#include <stdio.h>
#include <limits.h>

int main()
{
    // 输入
    unsigned long a, k;
    if( scanf("%lu %lu",&a,&k) != 2 )
        return -1;

    for( ; k; --k )
    {
        // 求去掉一个位的集合中最小元素
        unsigned long min = ULONG_MAX;
        for( unsigned long s=1; ; s*=10 )
        {
            unsigned long w = a%s;
            if( s <= a/10 )
                w += a/(s*10)*s;

            if( w < min )
                min = w;

            if( s > a/10 )
                break;
        }
        a = min;
    }
    printf( "%lu\n", a );

    return 0;
}

还想到一种非常快速的方法：
在 a 的前 k+1 位中，取最小的一个位，删除这个最小位之前的数。最小位之后的数 进行递归。

比如 a=5412873 k=3
则在前k+1=4位（“5413”）中取最小位，即1，删除1之前的所有数（即5和4）
余下 2873，还需要删除1一个数，即用 a=2874，k=1递归
……
a = 874, k=1
……
a = 74，k=0 结束

即需要删除5 4 8


[ 本帖最后由 rjsp 于 2011-4-18 13:46 编辑 ]

先MARK，上完课再来看看……

http://www.
上面有解释