首页 > 代码库 > ”高精度整数删去若干位以使剩下的值最小“问题

”高精度整数删去若干位以使剩下的值最小“问题

2024-07-14 22:23:54   224人阅读

问题描述：

键盘输入一个高精度的正整数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;}
View Code

 

 


联系
我们