杭州交通信息网飞行时间最长的航班:算法高手救命啊！！！！
来源：百度文库 编辑：杭州交通信息网 时间：2024/05/08 06:11:33
给定一个n位正整数a，去掉其中任意k<=n个数字后，剩下的数字按原次序排列组成一个新的正整数，对于给定的n位正整数a和正整数k，设计一个算法找出剩下数字组成的新数最小的删数方案！
请高手能给出算法，最好能附带源程序（c or java）!!!!
题目是 自己删除k个数字，不是随机的，还有，是按原顺序排列，不是按从小到大排！
请高手能给出算法，最好能附带源程序（c or java）!!!!
题目是 自己删除k个数字，不是随机的，还有，是按原顺序排列，不是按从小到大排！
我不是高手，仅说出自己的想法。
首先要把a的各位数字提取出来存入一个数组array[n]，接下来的才是难点.
去掉k个数，而且原序不变，剩下n-k个数，那么剩下数的最高位肯定是在左边k+1个数里。要想剩下的数最小，那么最高位肯定要是左边k+1个数中最小的数。找到这k+1个数中的最小数，假设是第k1个数，那么删除左边的k1-1个数，留下第k个数。接下来的问题就成了“给定一个n-k1位的整数，去掉k-1个数，要求剩下的数最小”，这和原问题本质上没有差别。因此可以用递归方法解决。