贪心算法-删数问题C++

男娘i 2024-03-24 11:13 173阅读 0赞

**目录**

一、题目

二：思路

代码

运行结果

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

## 一、题目 ##

有一个长度为n（n <= 240）的正整数，从中取出k（k < n）个数，使剩余的数保持原来的次序不变，求这个正整数经过删数之后最小是多少。

输入格式:  
n和k

输出格式:  
一个数字，表示这个正整数经过删数之后的最小值。

输入样例:

178543   4

结尾无空行  
输出样例:

### 二：思路 ###

思路：

对于删数问题，可以采用贪心算法来求解。贪心算法即每次都选择当前最优的方案，从而得到全局最优解。对于这道题，可以使用如下的贪心策略：

1.  从左往右扫描数字，找到第一个比自己右侧数字大的数字，将该数字删除；
2.  如果没有找到这样的数字，说明所有数字都是递增的，直接删除最后一个数字；
3.  重复上述过程，直到删除了k个数字为止。
4.  注意前导0的删除。

根据上述贪心策略，可以得到一个最小的新数字。

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

可以用坐标来形象表示过程：【每次删去最大数，再把剩下来的数连起来再删、再连，直到达到要求】

![60ddbfccc6044429992525ee1adddebd.png][]

### 贪心算法实现 ###

1.  定义一个字符串变量表示剩余的数字数字；
2.  遍历每个数字，如果当前数字小于结果字符串的最后一个数字，那么就将结果字符串的最后一个数字删除，并将计数器加1；
3.  将当前数字加入结果字符串；
4.  如果计数器达到要删除的数字的数量时，就退出循环；
5.  如果遍历完所有数字时，还没有达到要删除的数字的数量，就从结果字符串末尾删除数字直到满足要求；
6.  如果结果字符串的所有数字都是0，就返回0；否则去掉前导零，并输出结果。

#### 代码 ####

#include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        string n;  // 原始数字n
        int k;     // 需要删除的数字个数
        while (cin >> n >> k)
        {
            string res = "";   // 存储最终结果
            int len = n.size(); // 数字n的长度
    
            // 假如需要删除的数字个数大于等于数字n的长度，直接输出0
            if (k >= len)
            {
                cout << 0 << endl;
                continue;
            }
    
            int cnt = 0;  // 记录已经删除的数字个数
            for (int i = 0; i < len; i++)
            {
                while (cnt < k && !res.empty() && res.back() > n[i])
                {
                    // 如果需要删除的数字尚未全部删除，且新来的数字比当前的倒数第一个数字小
                    // 就把最后一个数字删除，并将已删除数字个数加1
                    res.pop_back();
                    cnt++;
                }
                res.push_back(n[i]);  // 将新的数字添加到结果字符串中
            }
    
            // 如果需要删除的数字还没删除完，再从结果字符串末尾删除
            while (cnt < k)
            {
                res.pop_back();
                cnt++;
            }
    
            // 去掉前导零，并输出结果
            int i = 0;
            while (i < res.size() && res[i] == '0') i++;
            if (i == res.size()) cout << 0 << endl;
            else cout << res.substr(i) << endl;
        }
        return 0;
    }

#### 运行结果 ####

![795d3e6a608a4e8393e9853e2b31a872.png][]

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

**只输入一遍【代码】**

#include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        string n;  // 原始数字n
        int k;     // 需要删除的数字个数
        cin >> n >> k;
    
        string res = "";   // 存储最终结果
        int len = n.size(); // 数字n的长度
    
        // 假如需要删除的数字个数大于等于数字n的长度，直接输出0
        if (k >= len)
        {
            cout << 0 << endl;
            return 0;
        }
    
        int cnt = 0;  // 记录已经删除的数字个数
        for (int i = 0; i < len; i++)
        {
            while (cnt < k && !res.empty() && res.back() > n[i])
            {
                // 如果需要删除的数字尚未全部删除，且新来的数字比当前的倒数第一个数字小
                // 就把最后一个数字删除，并将已删除数字个数加1
                res.pop_back();
                cnt++;
            }
            res.push_back(n[i]);  // 将新的数字添加到结果字符串中
        }
    
        // 如果需要删除的数字还没删除完，再从结果字符串末尾删除
        while (cnt < k)
        {
            res.pop_back();
            cnt++;
        }
    
        // 去掉前导零，并输出结果
        int i = 0;
        while (i < res.size() && res[i] == '0') i++;
        if (i == res.size()) cout << 0 << endl;
        else cout << res.substr(i) << endl;
    
        return 0;
    }

**运行结果**

![6a353ec8ca4a4c02a1c7b093f1a988bd.png][]

**前导0的删除【测试】**

![a976c681092b4c13bab1180bad673711.png][]

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

> **for (i = 0; (i < n.size() - 1) && (n\[i\] <= n\[i + 1\]); ++i);**
> 
> for循环中的条件判断语句是判断n数组中相邻两个元素的大小关系，如果前一个元素小于等于后一个元素，则继续循环，否则跳出循环。循环结束后，i的值为最后一个满足条件的元素的下标加1。
> 
> 这段代码是用来寻找最近的下降点的。
> 
> 对于原始数字n，从左往右扫描每个数字，如果当前数字小于等于后面一个数字，说明在这个位置之前的数字都比后面的数字小或者相等，此时并没有出现下降，需要继续往后扫描。
> 
> 当找到第一个当前数字大于后面一个数字的位置i时，说明在这个位置出现了下降，这个i就是最近的下降点。接下来就可以将i位置上的数字删除，达到删数的目的。
> 
> 而这段代码的实现就是在循环中通过 `i++` 不断向前扫描数字，直到找到下降点为止。同时，由于这里是使用分号结束 for 循环的，所以循环体内部的语句不会被执行，只有循环条件起到了作用。
> 
> 综上所述，这段代码的作用是找到最近的下降点，从而实现删数问题的解决。

> **int i = 0;** 
> 
> **while (i < n.size() && n\[i\] == '0') i++;**
> 
> **if (i == n.size()) cout << 0 << endl;**
> 
> **else cout << n.substr(i) << endl;** 
> 
> 这段代码用来删去剩余数字中的前导零，以保证输出的新数字是不含前导零的。
> 
> 具体实现思路如下：
> 
> 1.  定义一个变量i，表示第一个非零数字的位置；
> 2.  从左往右扫描每个数字，如果当前数字是0，就将变量i加1，继续往后扫描；
> 3.  如果遇到第一个非零数字时，就退出循环；
> 4.  如果所有数字都是0，则输出0；否则输出从第i个位置开始的所有数字。
> 
> 在这段代码中，可以使用 while 循环来实现上述逻辑。首先将变量i初始化为0，然后循环遍历整个数字n。在循环内部，判断当前数字是否为0，如果是0，则将i加1，继续往后扫描；如果遇到第一个非零数字时，就退出循环。
> 
> 在循环结束后，需要再次判断i和n.size()的关系，如果i等于n.size()，说明所有数字都是0，输出0即可；否则使用 `n.substr(i)` 函数截取从第i个位置开始到字符串末尾的子串并输出即可，这个子串就是不含前导零的新数字。
> 
> 综上所述，这段代码的作用是完成前导零的删除，得到不含前导零的最终结果。

#include <iostream>
    #include <string>
    using namespace std;
    
    int main()
    {
        string n;  // 原始数字n
        int k;     // 需要删除的数字个数
        cin >> n >> k;
    
        if (k >= n.size()) // 当要删除的数字个数k大于等于n的长度时，直接输出0
        {
            cout << 0 << endl;
            return 0;
        }
    
        while (k > 0)
        {
            // 寻找最近下降点
            int i;
            for (i = 0; (i < n.size() - 1) && (n[i] <= n[i + 1]); ++i);
            n.erase(i, 1);
            k--;
        }
    
        // 删去前导0
        int i = 0;
        while (i < n.size() && n[i] == '0') i++;
        if (i == n.size()) cout << 0 << endl;
        else cout << n.substr(i) << endl;
    
        return 0;
    }

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

**2.**

>  **while (number.size() > 1 && number\[0\] == '0')  
>  number.erase(0, 1);  
>  cout << number << endl;**
> 
> 这段代码的作用是删除数字前面的所有前导零，以保证输出的数字没有前导零。
> 
> 实现思路如下：
> 
> 1.  定义一个 while 循环，在循环内部检查当前数字是否存在前导零；
> 2.  如果当前数字的位数大于1并且第一位是0，就将第一位删除；
> 3.  继续往后扫描，直到不存在前导零为止。
> 
> 在这段代码中，循环条件 `number.size() > 1 && number[0] == '0'` 表示当数字长度大于1并且第一个数字是0时，循环条件成立。循环体内部的 `number.erase(0, 1)` 语句表示删除从第一个位置开始的1个字符，即删除第一个数字。
> 
> 这个循环会一直执行，直到不存在前导零为止。最终，输出的数字就是不含前导零的结果。
> 
> 综上所述，这段代码的作用是删除数字前面的所有前导零，得到不含前导零的最终结果。

#include<iostream>
    #include<string>
    using namespace std;
    int main() {
    	string number;
    	int k;
    	cin >> number >> k;
    
    	//有一个小问题。当要删除的数字个数k大于等于n的长度时，使用了number.erase()语句直接将原始数字全部删除，
    	// 但这会导致程序在接下来的操作中出错。
    	//if (k >= number.size())
    	//	number.erase();
    
    	if (k >= number.size()) // 当要删除的数字个数k大于等于n的长度时，直接输出0
    	{
    		cout << 0 << endl;
    		return 0;
    	}
    	else
    		while (k>0) {
    			//寻找最近下降点
    			int i;
    
    			//for循环中的条件判断语句是判断number数组中相邻两个元素的大小关系，
    			//如果前一个元素小于等于后一个元素，则继续循环，否则跳出循环。
    			//循环结束后，i的值为最后一个满足条件的元素的下标加1。
    			for (i = 0; (i < number.size() - 1) && (number[i] <= number[i + 1]); ++i);
    			number.erase(i, 1);
    			k--;
    		}
    	//删去前导0
    	while (number.size() > 1 && number[0] == '0')
    		number.erase(0, 1);
    	cout << number << endl;
    	return 0;
    }

[60ddbfccc6044429992525ee1adddebd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/77206c14f8df483b8e64ac1fe5c3498a.png
[795d3e6a608a4e8393e9853e2b31a872.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/b5a74818615f457a9df5c03b7cac916d.png
[6a353ec8ca4a4c02a1c7b093f1a988bd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/55593ef9daab4ef9bfbe584f1696dcad.png
[a976c681092b4c13bab1180bad673711.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/24/ae5203018d50479683996555b6e6b447.png