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

题目

删除字符 - 蓝桥云课

---

题目描述

给定一个单词，请问在单词中删除 $t$ 个字母后，能得到的字典序最小的单词是什么？

输入描述

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

第二行包含一个正整数 $t$ 。

其中，单词长度不超过 $100$ ， $t$ 小于单词长度。

输出描述

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

输入输出样例

示例 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);
    }
}