• C++入门必会--删数问题


    题目链接

    删数问题 - 洛谷https://www.luogu.com.cn/problem/P1106


    题目描述

           键盘输入一个高精度的正整数N(不超过250位),去掉其中任意K个数字后剩下的数字按原左右次序将组成一个新的非负整数。编程对给定的N和K,寻找一种方案使得剩下的数字组成的新数最小。

    输入

    输入两行正整数。

    第一行输入一个高精度的正整数N。

    第二行输入一个正整数K,表示需要删除的数字个数。

    输出

    输出一个整数,最后剩下的最小数。

    样例组

    1. 输入
    2. 175438
    3. 4
    4. 输出 13

    题目思路

            这是一道很经典的贪心题目。

            读入字符串s,然后读入N,紧接着对字符串s进行操作。这样做可以避免麻烦的高精度,从而借助字符串的特点(可以直接进行erase操作)来使题目更加简单。

            以样例为例,我们可以先列一张表格(表示字符串s),来模拟对字符串进行的删数操作。

            最开始的字符串是这样的:

    字符串sk=4
    175438

            然后我们根据数字比较大小先看首位,从而寻找最前面的逆序对(也就是前面的数比后面大的数对)。

    字符串sk=4
    175438

            然后可以发现,第一个逆序对是7和5,那么我们可以直接将7删去,从而让这个字符串在删除一个数的情况下最小。 

             以此类推,我们就可以将字符串s变成下表:

    字符串sk=1
    138

            那这时候该怎么删呢?我们可以用枚举的方法来将删除每个数位后的结果一一列出:

    1. 删除1后的结果: 38
    2. 删除3后的结果: 18
    3. 删除8后的结果: 13
    4. 38>18>13

             不难发现,在删除8后的结果最小。当整个字符串都不存在逆序对的时候,末尾的数最大。因此,在这种情况下,我们应该删除末尾的数。

            最后果然得出了正确答案13。


    题目解析

            那么该怎么具体实现删数问题呢?

            首先,输入部分一行cin就行了。而循环删数过程,我们可以使用while(k--)来执行。

            而每次删数,先设变量T为s.size()-1(最后一个数的位置),然后遍历字符串,寻找最前面的逆序对,并将T设为逆序对前面一个数的位置,直接切出循环。

            然后在循环外面写一行s.erase(T,1)将字符串的第T位删除。

            最后在while循环外面输出字符串s。

            题目主程序如下:

    1. void cx()
    2. {
    3. while(k--)//等价于for(int i=0;i
    4. {
    5. int t=s.size()-1;
    6. for(int j=0;j<=s.size();j++)
    7. {
    8. if(s[j]>s[j+1])//找到逆序对
    9. {
    10. t=j;//储存逆序对的前一位
    11. break;
    12. }
    13. }
    14. s.erase(t,1);//删除
    15. }
    16. }

            这一篇将会是题目解析/思路与标程分离的第一篇。之后与C++有关的内容都会将标程进行分离。涨粉1个,更新一篇!

  • 相关阅读:
    如何解决笔记本上有GPU但是torch.cuda.device_count()==0的问题?
    2.10_python+Django+mysql实现pdf转word项目_项目开发-编写pdf转word函数
    鸿蒙HarmonyOS实战-Web组件(基本使用和属性)
    Kafka3.x核心速查手册二、客户端使用篇-3、消息序列化机制
    操作系统与用户通信接口
    MYSQL4:慢查询的优化方法和锁机制
    ROS入门
    leetcode做题笔记135. 分发糖果
    OVER(PARTITION BY ***)用法,力扣mysql算法题,每日一题
    qt day6 人脸识别
  • 原文地址:https://blog.csdn.net/ceshyong/article/details/126094609