牛客 String II

示例1
输入
2,"abcde"
返回值
3

示例2
输入
10,"acesxd"
返回值
4

class Solution {
public:
    /**
     * 
     * @param k int整型 表示最多的操作次数
     * @param s string字符串 表示一个仅包含小写字母的字符串
     * @return int整型
     */
    int string2(int k, string s) {
        // write code here
        typedef pair<int,int> pii;
        vector<int> count(26, 0);
        for(auto c : s)
            count[c-'a']++; //计数
        int maxlen = 0;
        for(int i = 0; i < 26; ++i)
        {
            vector<pii> cost(26);
            for(int j = 0; j < 26; ++j)
                cost[j] = {abs(i-j), j};//cost花费, idx
            int num = k, len = 0;
            sort(cost.begin(), cost.end());//花费小的优先
            for(int j = 0; j < 26 && num > 0; ++j)
            {
                int ct = cost[j].first;//花费
                int id = cost[j].second;//字符id
                if(count[id] == 0)//字符没有的
                    continue;
                if(ct == 0)//花费为0的
                {
                    len += count[id];
                    continue;
                }
                int add = min(num/ct, count[id]);//可以拿的字符个数
                len += add;
                num -= add*ct;
            }
            maxlen = max(maxlen, len);
        }
        return maxlen;
    }
};