首页 > 代码库 > ”高精度整数删去若干位以使剩下的值最小“问题
”高精度整数删去若干位以使剩下的值最小“问题
问题描述:
键盘输入一个高精度的正整数N(不超过240位) ,去掉其中任意M个数字后剩下的数字按原左右次序将组成一个新的正整数。
编程对给定的N和M,寻找一种方案使得剩下的数字组成的新数最小。输出组成的新的正整数。
输入数据均不需判错。 如果去掉了某几个位后得到的新整数开头为0,保留0。
输入:
本题有多组测试数据,每组测试数据占一行。
一个高精度正整数N(N不超过240位)一个正整数M。(M为不大于N的长度的正整数)
N,M由一个空格分开。
456547 1
456547 2
456547 3
7773359 2
103 1
输出:
新的正整数,每组数据的输出占一行。不要多余的空白.
45547
4547
447
73359
03
问题分析:
在位数固定前提下,让高位的数字尽量小,其值就较小。依据贪心策略可以解决这个问题。
如何根据贪心来删除数字呢?总目标是删除高位较大的数字,具体地:相邻两位比较,若高位比地位大则删除高位。
但是看下面的特殊情况:
N="1234567" M=3
经过对N相邻位进行比较,一个数字也没删除,这就要将后3位删除。如果在相邻比较的过程中删除的位数小于M,也要进行相似的操作。
算法设计:
删除字符的实现方法很多,如:1.物理的进行字符删除。2.记录状态。3.。。。
代码如下:
# include<iostream>//# include<stdio.h>using namespace std;# include<string>int main(){ string n; int m; int i, j, k, l; while (cin >> n >> m) { l = 0; for (string::iterator it = n.begin(); it != n.end(); it++) { l++; } if (l == m) { cout << 0 << endl; } else { k = 0; i = 0; while (k < m&&i < l - 1) { if (n[i]>n[i + 1]) { for (j = i + 1; j < l; j++) { n[j - 1] = n[j]; } i = i == 0 ? 0 : i--;//not forget i--,and if i<0 then i=0 k++; } else { i++; } } for (i = 0; i < l - m; i++)//imatate cuting last l-m chars { cout << n[i]; } cout << endl; } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。