[TOC]

一、问题描述

    以前，西藏是农奴社会，每个农奴主都拥有数目众多的农奴，这些农奴的整个生命都是农奴主的，农奴主可以随便处死任意一名农奴。
    解放西藏时，政府为了保持农奴主的利益和西藏的和平，并没有立刻废除农奴制度，倒是一些农奴主没有丝毫地改变旧习惯，打死农奴的情况时有发生。
    这天，一个小农奴主又在为难农奴们了，他把他家每一条耗牛背上都写上了一个个位数字（0--9），然后把任意一些牛排在一起，这样就组成了一个多位数字。
    现在他为难大家的难题是，对于牛组成的这个多位数字，他每次会扔出几颗石头，扔出几颗石头就表示需要农奴们从那排牛中赶走多少头牛，这样剩下的牛不改变顺序又组成了一个新的数字，他的要求是，这个新的数字必须要最小。
    如果大家完成不了他的难题，那么每个农奴都要挨打，要知道他打人可是出了名的，不知道有多少个农奴被他打死了。
    请编写一个程序完成这项任务，然后夺下农奴主手里的皮鞭。

输入格式

N I （N是由牛背上的数字排成的多位数，已经牛的数量最少为2，最多为100，I表示扔出的石头的数量，即要从牛中赶走I头牛）

输出格式

S （赶走I头牛后剩下的牛组成的数字，要求这个新的数字最小）

输入输出样例

输入：
1432 2
输出样例：
12

二、问题分析

    这里简单来说：把 N 条牛上的数字组成一个数组，由于不改变顺序的，因此，牵走 I 条牛后，剩下的数组按顺序组成一个最小的数。
     那么什么样的数字最小呢？在位数相同的情况下，肯定是首位最小的值相对小些，然后第二位也取最小值... 依此类推
那么，比如说：3257296  3，我们第一次找到首位最小值：2，接下来找第二最小值 2 然后是9和6

那么怎么确定每个数的查找范围呢？
以上上面的分析为例：在3257296 里面牵走3头牛，那么剩下的牛的数量是4，我们找首位的时候只能从3257里面找，为什么？因为你在后面找到最小值了，那剩下的牛的数量就不够了。第一次最小值是 2。
第二次：确定了首位是2，是前面一个2，那第二次我们查找的位置就是从2后面的那个数字开始，结束位置是还有剩下3条牛的位置：后面的2，即：572里面找最小值，结果为2
第三次查找的位置是从9开始，留下1条牛，那么只有9能选择
第四次查找位置是从6开始，已经到了结束位置，因此最终结果为 2296

分析图

原始数据 第一次遍历 第二次 第三次 第四次 最终

三、JAVA代码

这里只放出核心代码

    /**
     * @param array 原始数组
     * @param m     剩余的个数，不是删除的个数
     * @return
     */
    private static int[] findMin(int[] array, int m) {

        // 校验
        if (m < 0) {
            throw new RuntimeException("m is invalid:" + m);
        }

        int len = array.length;

        if (m > len) {
            throw new RuntimeException("m is too large:" + m + ", the max m is " + len);
        }

        int[] res = new int[m];

        // 起始位置
        int start = 0;

        // 结束位置，需要减 m 是因为保证留下的数字数量
        int end = len - m;

        for (int i = 0; i < m; i++) {

            // 查找此区间的最小值
            for (int j = start + 1; j <= end; j++) {

                if (array[start] > array[j]) {
                    start = j;
                }
            }

            // 将最小值保存到新数组中
            res[i] = array[start];

            // 开始位置右移
            start++;

            // 结束位置右移，因为取到一个数字后，就可以向后多取一位了
            end++;
        }
        return res;
    }

三、测试

我们使用 3257296 从0测试到最大值
下面是测试代码

    public static void main(String[] args) {

        int[] array = {3, 2, 5, 7, 2, 9, 6};

        // 牵走的牛
        for (int i = 0; i <= array.length; i++) {
            test(array, array.length - i);
        }

    }

    private static void test(int[] arr, int m) {
        int[] res = findMin(arr, m);

        System.out.print("剩余 " + m + ":");
        for (int i : res) {
            System.out.print(i);
        }

        System.out.println();
    }

输出的结果

剩余 7:3257296
剩余 6:257296
剩余 5:25296
剩余 4:2296
剩余 3:226
剩余 2:22
剩余 1:2
剩余 0:

四、总结

总体来说难度还好，就是需要分析清楚里面的逻辑，开始我直接去除里面的最大值，没有考虑位置问题，走了一些弯路。

当然如果有其他更好的办法也可以留言。