侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【贪心算法】删除字符【蓝桥杯】

GabrielxD
2023-03-25 / 0 评论 / 0 点赞 / 129 阅读 / 332 字
温馨提示:
本文最后更新于 2023-03-25,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

删除字符 - 蓝桥云课


题目描述

给定一个单词,请问在单词中删除 tt 个字母后,能得到的字典序最小的单词是什么?

输入描述

输入的第一行包含一个单词,由大写英文字母组成。

第二行包含一个正整数 tt

其中,单词长度不超过 100100tt 小于单词长度。

输出描述

输出一个单词,表示答案。

输入输出样例

示例 1

输入

LANQIAO
3

输出

AIAO

运行限制

  • 最大运行时间:1s
  • 最大运行内存: 128M

解题

方法一:贪心算法

思路

长度字符组成相同的情况下,让字符串字典序最小的方法是按照字典序升序排序。知道了这一点,就知道了这题的做法:

尽可能优先删去字符串中靠前的逆序对,若已经没有逆序对了,就优先删除末尾字符。

代码

import java.util.*;
import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        Scanner in = new Scanner(System.in);
        StringBuilder s = new StringBuilder(in.nextLine());
        int t = in.nextInt();
        while (t-- > 0) {
            int i = 0;
            for (; i < s.length() - 1; ++i) {
                if (s.charAt(i) > s.charAt(i + 1)) break;
            }
            s.deleteCharAt(i);
        }
        System.out.println(s);
    }
}
0

评论区