D. Not a Cheap String - 题解

比赛与标签

比赛: Codeforces Round 805 (Div. 3) 标签: greedy, *1000 难度: *1000

题目大意喵~

主人，这道题是这样的呐：

我们有一个由小写字母组成的字符串 w 和一个整数 p。每个字母都有一个“价格”，'a' 是 1，'b' 是 2，...，'z' 是 26。一个字符串的总价格就是它所有字母价格的总和。

我们的任务是，从字符串 w 中删除 最少数量 的字母，使得剩下字符串的总价格小于或等于 p。当然啦，删除字母后，剩下字母的相对顺序是不能改变的哦。

比如说，如果 w 是 "abca"，它的价格是 1+2+3+1=7。如果 p 是 2，我们就需要删掉一些字母。如果我们删掉 'b' 和 'c'，剩下 "aa"，价格是 1+1=2，就满足要求啦！

输入：

第一行是一个整数 t，表示有 t 组测试数据。
每组数据包含一个字符串 w 和一个整数 p。

输出：

对于每组数据，输出一个处理后的字符串。

解题思路呐！

要删除最少的字母，反过来想，不就是要保留最长的字符串嘛？对不对呀？喵~

那么，当我们发现原始字符串 w 的总价格超过了预算 p 时，我们就必须开始“省钱”了。为了让字符串尽可能长，我们每次删除操作都应该尽可能地降低总价格。

想一想，删除哪个字母最“划算”呢？当然是价格最高的那个啦！比如说，删除一个 'z' 可以让价格瞬间减少 26，而删除一个 'a' 只能减少 1。为了用最少的删除次数达到目标价格，我们肯定优先删除那些“贵”的字母，对吧？

这就是我们的 贪心策略 啦！

计算初始价格：首先，我们遍历一遍字符串 w，计算出它的总价格 current_price。如果 current_price <= p，那太棒了！我们一个字母都不用删，直接输出 w 就好啦。
决定删除哪些字母：如果价格超了，我们就得开始删了。按照我们的贪心策略，我们应该从最贵的字母 'z' 开始考虑。
- 看看字符串里有几个 'z'。
- 只要总价格还大于 p，并且我们还有 'z' 可以删，就删掉一个 'z'，然后更新总价格。
- 如果 'z' 删完了价格还超标，那我们就开始考虑第二贵的 'y'，然后是 'x'，以此类推，直到总价格达标为止。
如何高效地执行删除：一个一个删太慢啦！我们可以先用一个频率数组 counts 统计 w 中每个字母出现的次数。再用另一个数组 remove_counts 来记录我们需要从 w 中删除的每种字母的数量。我们从 'z' 遍历到 'a'，计算需要删除多少个当前字母才能让价格达标，然后更新 remove_counts。
构建最终字符串：在确定了需要删除哪些字母（以及数量）之后，我们就要构建最终结果了。为了保持原有顺序，我们再次遍历原始字符串 w。对于 w 中的每一个字符 c：
- 我们查一下 remove_counts，看看我们是否需要删除一个 c。
- 如果需要 (remove_counts[c-'a'] > 0)，我们就跳过这个字符，并把 remove_counts[c-'a'] 减一，表示我们已经用掉了一个“删除名额”。
- 如果不需要，我们就把它加到我们的答案字符串 result 中。

这样一趟下来，我们就能得到一个又满足价格要求、又保留了原始顺序、并且还是最长的字符串啦！是不是很清晰呢？喵~

代码实现喵~

下面是AC代码的实现，小猫娘已经加上了详细的注释，方便主人理解每一行都在做什么哦！

cpp

#include <iostream>
#include <string>
#include <vector>
#include <numeric>
#include <algorithm>

void solve() {
    std::string w;
    std::cin >> w;
    int p;
    std::cin >> p;

    long long current_price = 0;
    // counts[0] 存 'a' 的数量, counts[1] 存 'b' 的数量, ...
    std::vector<int> counts(26, 0); 
    
    // 第一步：计算初始总价和每个字符的频率
    for (char c : w) {
        current_price += (c - 'a' + 1);
        counts[c - 'a']++;
    }

    // 如果初始价格已经满足要求，直接输出原字符串
    if (current_price <= p) {
        std::cout << w << "\n";
        return;
    }

    // 第二步：决定要删除哪些字符 (贪心策略)
    // remove_counts[i] 表示要删除 ('a'+i) 这个字符的数量
    std::vector<int> remove_counts(26, 0); 
    // 从最贵的字符 'z' 开始，往下到 'a'
    for (int i = 25; i >= 0; --i) {
        // 如果价格已经达标，就不用再删了
        if (current_price <= p) {
            break;
        }

        int price_of_c = i + 1; // 当前字符的价格
        int num_available = counts[i]; // 当前字符在字符串中的总数

        if (num_available == 0) {
            continue; // 如果这个字符本来就没有，就跳过
        }
        
        // 计算需要减少多少价格
        long long excess = current_price - p;
        // 计算为了达到目标，最少需要删除多少个当前字符
        // (excess + price_of_c - 1) / price_of_c 是向上取整的写法，确保减够
        long long can_remove_to_reach_target = (excess + price_of_c - 1) / price_of_c;
        // 实际能删除的数量，是“需要的数量”和“拥有的数量”中的较小者
        int num_to_remove = std::min((long long)num_available, can_remove_to_reach_target);

        // 更新总价格和要删除的字符数量
        current_price -= (long long)num_to_remove * price_of_c;
        remove_counts[i] = num_to_remove;
    }

    // 第三步：根据删除计划，构建最终字符串
    std::string result = "";
    for (char c : w) {
        // 检查这个字符是否在我们的删除名单上
        if (remove_counts[c - 'a'] > 0) {
            // 如果是，就用掉一个删除名额，并且不把它加入结果字符串
            remove_counts[c - 'a']--;
        } else {
            // 如果不是，就把它保留下来
            result += c;
        }
    }
    std::cout << result << "\n";
}

int main() {
    // 加速输入输出，对付大数据量很有用哦！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

复杂度分析的说

时间复杂度: O(N) 的说。其中 N 是字符串 w 的长度。
- 我们对字符串 w 进行了两次完整的遍历：一次是计算初始价格和频率，一次是构建最终结果。两次都是 O(N) 的。
- 中间那个决定删除哪些字符的循环，最多只会执行 26 次（从 'z'到'a'），这是一个常数时间的操作，所以是 O(1)。
- 所以总的时间复杂度就是 O(N) + O(1) + O(N) = O(N)，非常快呢！
空间复杂度: O(1) 的说。
- 我们使用了 counts 和 remove_counts 两个数组，它们的大小都是 26，是固定的常数。
- 结果字符串 result 的空间不算在辅助空间复杂度里。所以我们使用的额外空间是恒定的，和输入规模 N 无关。

知识点与总结

这道题真是一道非常经典的 贪心算法 教学题呢，喵~

核心思想 - 贪心 (Greedy): 解决问题的关键在于找到正确的贪心策略。在这里，就是“每次都移除价值最高的字符”。这个选择在局部看起来最优，并且最终能导向全局最优解（删除最少的字符）。
数据结构 - 频率数组 (Frequency Array): 当处理的对象是固定范围的字符或数字时（比如小写字母），使用频率数组来计数是一种非常高效、简洁的技巧。
实现技巧 - 两遍扫描 (Two-pass Scan): 这是一个很常见的解题模式。第一遍扫描收集信息和做出决策，第二遍扫描根据决策来构建最终的答案。这样做的好处是逻辑清晰，并且能轻松处理需要保持原序列相对顺序的问题。
小细节要注意哦:
- 价格总和可能会很大，所以用 long long 来存储 current_price 是个好习惯，可以避免溢出。
- 记住，我们的目标是删除最少的字符，这等价于保留最长的字符串。时刻想着这个最终目标，就能帮助我们找到正确的贪心方向！

好啦，今天的题解就到这里啦！希望小猫娘的讲解能帮到你哦！继续加油，下一道题也一定能轻松AC的！喵~ (ฅ'ω'ฅ)

D. Not a Cheap String - 题解 ​

比赛与标签 ​

题目大意喵~ ​

解题思路呐！ ​

代码实现喵~ ​

复杂度分析的说 ​

知识点与总结 ​