文章

119

粉丝

68

获赞

90

访问

19.9k

头像
选球问题 题解:这不是dp,刚开始看成限长增长子序列了,直接排序贪心即可
P1683 中南大学2019年机试题
发布于2025年2月18日 16:34
阅读数 26

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, k;
    while (cin >> n >> k) {
        string s;
        cin >> s;
        sort(s.begin(), s.end()); // 按权值从小到大排序

        int total_weight = 0; // 总权重和
        char last_char = '\0'; // 上一个选的球
        int count = 0; // 已选球的数量

        for (int i = 0; i < n; i++) {
            if (count >= k) break; // 已选够 k 个球
            if (last_char == '\0' || s[i] - last_char >= 2) {
                // 如果满足条件,选择当前球
                total_weight += (s[i] - 'a' + 1); // 计算权重
                last_char = s[i]; // 更新上一个选的球
                count++; // 已选球数量加 1
            }
        }

        if (count < k) {
            // 如果选不出 k 个球,输出 -1
            cout << -1 << endl;
        } else {
            // 输出最小权重和
            cout << total_weight << endl;
        }
    }
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发