【洛谷 P1106】删数问题 题解(贪心+字符串)

这篇具有很好参考价值的文章主要介绍了【洛谷 P1106】删数问题 题解(贪心+字符串)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

删数问题

题目描述

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

输入格式

输入两行正整数。

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

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

输出格式

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

样例 #1

样例输入 #1

175438 
4

样例输出 #1

13

思路

将 n 作为字符串读入,并在 n 末尾添加一个 0 ,方便比较。

使用贪心算法,删除递减序列。如果当前数字大于等于下一个数字,则删除当前数字。

注意:结果要移除前导零再输出。文章来源地址https://www.toymoban.com/news/detail-723117.html


AC代码

#include <iostream>
#define AUTHOR "HEX9CF"
using namespace std;

int main()
{
    string n;
    int k;
    cin >> n >> k;
    n += '0';
    while (k)
    {
        for (int i = 0; i < n.length() - 1; i++)
        {
            if (n[i] > n[i + 1])
            {
                string a = n.substr(0, i);
                string b = n.substr(i + 1, n.length() - i - 1);
                // cout << a << " " << b << endl;
                n = a + b;
                k--;
                break;
            }
        }
    }
    int index = n.find_first_not_of('0');
    // cout << index << endl;
    if (!~index)
    {
        index = 0;
    }
    n = n.substr(index, n.length() - index - 1);
    cout << n << endl;
    return 0;
}

到了这里,关于【洛谷 P1106】删数问题 题解(贪心+字符串)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 《热题100》字符串、双指针、贪心算法篇

    思路:对于输入的的字符串,只有三种可能,ipv4,ipv6,和neither ipv4:四位,十进制,无前导0,小于256 ipv6:八位,十六进制,无多余0(00情况不允许),不为空 class Solution:     def solve(self , IP: str) - str:         if \\\'.\\\' in  IP: #有可能是IPV4             res = IP.split(\\\'.\\\')            

    2024年02月09日
    浏览(43)
  • 【洛谷 P1996】约瑟夫问题 题解(数组+模拟+循环)

    n n n 个人围成一圈,从第一个人开始报数,数到 m m m 的人出列,再由下一个人重新从 1 1 1 开始报数,数到 m m m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。 注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n − 1

    2024年02月07日
    浏览(36)
  • 有效的括号字符串(力扣)动态规划、贪心 JAVA

    给你一个只包含三种字符的字符串,支持的字符类型分别是 ‘(’、‘)’ 和 ‘*’。请你检验这个字符串是否为有效字符串,如果是有效字符串返回true 。 有效字符串符合如下规则: 任何左括号 ‘(’ 必须有相应的右括号 ‘)’。 任何右括号 ‘)’ 必须有相应的左括号 ‘(’

    2024年02月14日
    浏览(40)
  • (贪心) 1221. 分割平衡字符串 ——【Leetcode每日一题】

    难度:简单 平衡字符串 中, \\\'L\\\' 和 \\\'R\\\' 字符的数量是相同的。 给你一个平衡字符串 s ,请你将它分割成尽可能多的子字符串,并满足: 每个子字符串都是平衡字符串。 返回可以通过分割得到的平衡字符串的 最大数量 。 示例 1: 输入:s = “RLRRLLRLRL” 输出:4 解释:s 可以分

    2024年02月11日
    浏览(34)
  • 【string题解 C++】字符串相乘 | 翻转字符串III:翻转单词

    目录 字符串相乘 题面 错误记录 Way1 拆分成“先乘后加” 思路 实现 时空复杂度分析 反思 Way2 用数组 思路 实现 时空复杂度分析 翻转字符串III:翻转字符串中的单词 题面 错误记录 思路1 遍历找单词 实现 思路2 暴力解法 实现 力扣(LeetCode)官网 - 全球极客挚爱的技术成长平

    2024年02月07日
    浏览(62)
  • python - leetcode - 424. 替换后的最长重复字符【经典题解 - 贪心滑动窗口算法】

    描述: 给你一个字符串 s 和一个整数 k 。你可以选择字符串中的任一字符,并将其更改为任何其他大写英文字符。该操作最多可执行 k 次。 在执行上述操作后,返回包含相同字母的最长子字符串的长度。 示例 1: 示例 2: 提示: 1 = s.length = 105 s 仅由大写英文字母组成 0 =

    2024年02月16日
    浏览(47)
  • LeetCode-763. 划分字母区间【贪心 哈希表 双指针 字符串】

    给你一个字符串 s 。我们要把这个字符串划分为尽可能多的片段,同一字母最多出现在一个片段中。 注意,划分结果需要满足:将所有划分结果按顺序连接,得到的字符串仍然是 s 。 返回一个表示每个字符串片段的长度的列表。 示例 1: 输入:s = “ababcbacadefegdehijhklij” 输

    2024年04月10日
    浏览(56)
  • python/c++ Leetcode题解——2744. 最大字符串配对数目

    我们可以直接使用二重循环,枚举给定的数组 words 中的 words[i] 和 words[j] 是否可以匹配。 由于题目规定了数组 words 中包含的字符串互不相同,因此在枚举时,只要保证 ij,那么每个字符串最多匹配一次。 C++: python:

    2024年01月17日
    浏览(48)
  • leetcode2434. 使用机器人打印字典序最小的字符串 出栈顺序 贪心+栈

    https://leetcode.cn/problems/using-a-robot-to-print-the-lexicographically-smallest-string/         给你一个字符串 s 和一个机器人,机器人当前有一个空字符串 t 。 执行以下操作之一 ,直到 s 和 t 都变成空字符串。请你返回 纸上能写出的字典序最小的 字符串: 操作一:删除字符串 s 的 第

    2024年02月14日
    浏览(39)
  • 【力扣·每日一题】2182.构造限制重复的字符串(模拟 贪心 优先队列 C++ Go)

    题目链接 给你一个字符串 s 和一个整数 repeatLimit ,用 s 中的字符构造一个新字符串 repeatLimitedString ,使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。 返回 字典序最大的 repeatLimitedString 。 如果在字符串 a 和 b 不同的第一个位置,字符串 a 中

    2024年01月17日
    浏览(54)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包