字符串价值

每次最高位减1，然后记得每次都得重新排序= =
#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int main()
{
    string str;
    int k;
    while (cin >> str >> k)
    {
        int  a[26] = { 0 };
        for (int i = 0;i < str.size();i++)
            a[str[i] - 'a']++;     //对应位加1
        sort(a, a + 26);
        int i = 0;
        while (k)
        {
            a[25]--;          //每次都减最高位这样得到的价值最低
            sort(a, a + 26); //每次都需要重新排序
            k--;        
        }
        int sum = 0;
        for (int i = 0;i < 26;i++)
        {
            sum += a[i] * a[i];
        }
        cout << sum << endl;
    }
    return 0;
}

python解法

from collections import Counter

string, k = input(), int(input())
arr = sorted(Counter(string).values())
for i in range(k):
    arr[-1] -= 1
    arr.sort()
print(sum(map(lambda c: c ** 2, arr)))

思路是不断将出现最多次的字符数量减1。
最后将所有字符出现次数平方和加起来。

将出现次数最多的字符数量减1后，该字符数量可能不是最多的了，所以要作下sort操作，找到出现次数最多的那个。

#include<iostream>
#include<algorithm>

using namespace std;

int main() {
    string s;
    int k;
    cin >> s >> k;
    int alph[26] = {0};
    for (int i = 0; i < s.size(); i++) {
        alph[s[i] - 'a']++;
    }
    sort(alph, alph + 26);
    for (int i = 0; i < k; i++) {
        alph[25]--;
        sort(alph, alph + 26);
    }
    int value = 0;
    for (int i = 0; i < 26; i++) {
        value += alph[i] * alph[i];
    }
    cout << value << endl;
    return 0;
}

import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.next(),in.nextInt()));
        }
    }
    public static int helper(String s,int k){
        char[] cs = s.toCharArray();
        int[] a = new int[26];
        for(char c:cs){
            a[c - 'a']++;
        }
        //不用自己造轮子系列
        PriorityQueue<Integer> pq = new PriorityQueue<>((o1,o2)->{
            return o2 - o1;
        });
        for(int num:a){
            if(num != 0) pq.add(num);
        }
        int i = 0;
        while(i < k){
            int num = pq.remove();
            pq.add(num - 1);
            i++;
        }
        int sum = 0;
        for(int num:pq){
            sum += num * num;
        }
        return sum;
    }
}

//每次最大的值减一，得到的价值最小。
import java.util.*;
public class Main {
    public static int pingfang(int a[]){
        int sum=0;
        for(int i=0;i<a.length;i++)
            sum+=a[i]*a[i];
        return sum;
    }
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String str=in.nextLine();
        int k=in.nextInt();
        HashMap<Character,Integer> map=new HashMap();
        for(int i=0;i<str.length();i++){
            char c=str.charAt(i);
            if(!map.containsKey(c))
                map.put(c, 1);
            else{
                map.put(c, map.get(c)+1);
            }
                
        }
        List<Integer> list=new ArrayList(map.values());
    //    System.out.println(list.values().toString());
        int a[]=new int[list.size()];
        for(int i=0;i<list.size();i++){
            a[i]=list.get(i);
        }
        
        for(int i=0;i<k;i++){
            Arrays.sort(a);
            a[a.length-1]--;
        }
        System.out.println(pingfang(a));

        
    }

}

	

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int k = sc.nextInt();
        int sum = 0;
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < str.length(); i++) {
            if (map.containsKey(str.charAt(i))) {
                map.put(str.charAt(i), map.get(str.charAt(i)) + 1);
            } else {
                map.put(str.charAt(i), 1);
            }
        }
        int[] arr = new int[map.size()];
        int i = 0;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            arr[i++] = entry.getValue();
        }
        Arrays.sort(arr);

        while (k-- > 0) {
            arr[arr.length - 1] -= 1;
            Arrays.sort(arr);
        }
        for (i = 0; i < arr.length; i++) {
            sum += arr[i] * arr[i];
        }
        System.out.println(sum);
    }
}

//最大减一

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
bool compare(int a, int b)
{
    return a>b;
}
int main(int argc, char** argv)
{
    string s;
    int k, con[26] = { 0 }, value = 0;
    cin >> s >> k;
    for (auto i = 0; i < s.size(); ++i)
    {
        ++con[s[i] - 'a'];
    }
    sort(con, con + 26,  compare);
    for (int i = 0; i < k; ++i)
    {
        --con[0];
        sort(con, con + 26, compare);
    }
    for (int i = 0; i < 26; ++i)
    {
        value += con[i]*con[i];
    }
    cout << value << endl;
    system("pause");
}

只需要一次排序，每次减操作不需要进行额外的排序，直接找到原最大数减1后的位置插入即可。

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
int map[26];
int main(){
    string s;
    int k;
    cin >> s >> k;
    for(int i = 0;i < s.size();i++)
        map[s[i] - 'a']++;
    sort(map, map + 26);
    for(int i = 0;i < k;i++){
        map[25] -= 1;
        int temp = map[25];
        for(int j = 24; j >= 0;j--){
            if(map[j] > temp)
                swap(map[j], map[j + 1]);
            else
                break;
        }
    }
    int ans = 0;
    for(int i = 0;i <= 25;i++)
        ans += map[i] * map[i];
    cout<<ans<<endl;
    return 0;
}

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
int main(){
    string str;
    cin >> str;
    int k,rec=0,rev=0,sum=0;//rec为字符串的长度,rev为字符串出现的字母的个数
    cin >> k;
    int a[26] = { 0 };
    for (auto s : str){
        a[s - 'a']++;
    }
    for (int i = 0; i < 26; i++){
        if (a[i] > 0){
            rec += a[i];
            rev++;
        }
    }
    if ((rec - rev) < k)
        cout << rec - k << endl;
    if ((rec - rev) == k)
        cout << rev << endl;
    if ((rec - rev)>k){
        for (int i = 0; i < k; i++){
            sort(a, a + 26);
            a[25]--;
        }
        for (int i = 0; i < 26; i++){
            sum += pow(a[i],2);
        }
        cout << sum << endl;
    }
    system("pause");
    return 0;
}

s=list(input())
k=int(input())
ss=set(s)
sum=0
cou=[]
##统计不同字符的个数
for item in ss:
    cou.append(s.count(item))        
if k!=0:
    while sum!=k:                  #操作次数不为给定数
        cou_max=max(cou)         #字符个数最大值
        cou[cou.index(cou_max)]-=1     #最大值个数减一
        sum+=1                         #操作次数加一
    res=0
    for x in cou:
        res+=x*x
    print(res)
else:
    res=0
    for x in cou:
        res+=x*x
    print(res)

    private static int solve(String string, int k) {
        int result = 0;
        HashMap<Character, Integer> hashMap = new HashMap<>();
        for (Character character : string.toCharArray()) {
            Integer value = hashMap.get(character);
            hashMap.put(character, value == null ? 1 : value + 1);
        }
        
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(hashMap.size(), new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2.compareTo(o1);
            }
        });
        priorityQueue.addAll(hashMap.values());
        for (int i = 0; i < k; i++) {
            priorityQueue.offer(priorityQueue.poll() - 1);
        }
        for (Integer integer : priorityQueue) {
            result += integer * integer;
        }
        return result;
    }

from collections import Counter
s = input()
n = int(input())
l = list(dict(Counter(s)).values())
for i in range(n):
    l.sort()
    l[-1] -= 1
res = 0
for i in l:
    res += i ** 2
print(res)

s = input()
#移除最多k个字符
k = (int)(input())
stat = [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(len(s)):
    stat[ord(s[i])-96]+=1
#按由小到大顺序排序
stat.sort()
#让最大的数排在最前面
stat.reverse()
#用来存储，一共有多少种英文字母
e_num = 0
x  = 0
while(stat[x]!=0):
    e_num+=1
    x+=1
#将stat列表精简为stat_1,新列表只存储出现过的英文字母的出现次数。
stat_1 = list(range(e_num))
for i in range(e_num):
    stat_1[i] = stat[i]

#循环k次，每次循环里，把当前最大的数减一即可。
for i in range(1, k+1):
    for q in range(e_num):
        if(stat_1[q]==max(stat_1)):
            stat_1[q]-=1
            break
#价值最小值
count = 0
for i in range(len(stat_1)):
    count = count + stat_1[i]*stat_1[i]
print(count)

#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<cstring>
#include<vector>
#include<math.h>
using namespace std;
int main(){
    //所有字符次数的平方和作为字符串的价值
    string s;
    cin >> s;
    int k;
    cin >> k;
    
    int appear[26];
    memset(appear, 0, sizeof(appear));
    for(int i = 0; i < s.size(); i++){
        appear[s[i] - 'a'] ++;
    }
    while(k > 0){
        //每个循环记录max1和max2的位置
        int max1 = 0, max2 = 0;
        int pos1 = 0, pos2 = 0;
        for(int i = 0; i < 26; i++){
            if(appear[i] > max1){
                max2 = max1;
                pos2 = pos1;
                max1 = appear[i];
                pos1 = i;
            }
            else if(appear[i] > max2){
                max2 = appear[i];
                pos2 = i;
            }
        }
        if(max1 - max2 + 1 < k){
            appear[pos1] = appear[pos1] - (max1 - max2 + 1);
            k = k - (max1 - max2 + 1);
        }
        else{
            appear[pos1] = appear[pos1] - k;
            k = 0;
        }
    }
    int sum = 0;
    for(int i = 0; i < 26; i++){
        sum += appear[i] * appear[i];
    }
    cout << sum << endl;
}

# coding=utf-8

def fun():
    s = raw_input()
    k = int(raw_input())
    Alphabet = [0]*26
    for i in range(len(s)):
        Alphabet[ord(s[i])-ord('a')] += 1
    for i in range(k):
        Alphabet.sort()
        Alphabet[-1] -= 1 #每次移除出现最多次的字符
    result = 0
    for i in range(len(Alphabet)):
        result += Alphabet[i] * Alphabet[i]
    return result

if __name__=='__main__':
    print(fun())

s = input().strip()
k = eval(input())
a_d = dict()
for m in s:
    if m not in a_d:
        a_d[m] = 1
    else:
        a_d[m] += 1
for n in range(k):
    k_m = max(a_d, key = a_d.get)
    a_d[k_m] -= 1
v = a_d.values()
res = 0
for w in v:
    res += w * w
print(res)

let str = readline();
let k = parseInt(readline(),10);
function output(str,k){
            let obj = {},arr=[],result=0;
            for(let i = 0; i < str.length; i++) {
                if(obj[str[i]]) {
                    obj[str[i]]++;
                } else {
                    obj[str[i]] = 1;
                }
            }
            for(key in obj){
                arr.push(obj[key]);
            }
            arr.sort(function(a,b){
                return a-b;
            });
            let len = arr.length - 1;
            for(let i = 0; i < k; i++) {
                arr[len]--;
                arr.sort(function(a,b){
                    return a-b;
                });
            }
        arr.forEach(function(val){
                result += val*val;
        })
        return result;
    }
console.log(output(str,k));

#include<stdio.h>
#include<queue>
#include<map>
using namespace std;
int main(){
    map<char,int> book;
    char s[100];
    int i,k,x,res=0;
    for(scanf("%s%d",s,&k),i=0;s[i]!='\0';i++) book[s[i]]++;
    priority_queue<int> Q;
    map<char,int>::iterator it;
    for(it=book.begin();it!=book.end();it++) Q.push(it->second);
    while(k--) x=Q.top()-1,Q.pop(),Q.push(x);
    while(!Q.empty()) res+=Q.top()*Q.top(),Q.pop();
    printf("%d\n",res);
}

#include <bits/stdc++.h>

using namespace std;

bool cmp(int a, int b){     return a>b;
}

int main()
{     string s;     int k;     while(cin>>s>>k){          int a[26] = {0};         for(int i=0;i<s.length();i++)             a[s[i]-'a']++;         sort(a,a+26,cmp);                 while(k>0){             for(int i=1;i<26,a[i-1]>0;i++){                 if(a[i]==0 || a[i]<a[i-1]){                     a[i-1]--;                     k--;                     break;                 }             }         }         int s = 0;         for(int i=0;i<26;i++){             if(a[i]!=0)                 s += a[i]*a[i];             else                 break;         }         cout<<s<<endl;     }     return 0;
}

import java.util.*;
public class Main{
    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        String s = in.nextLine();
        int k = in.nextInt();
        int sum = 0;
        TreeMap<Character, Integer> map = new TreeMap();   // 统计每个字母的个数
        for(int i=0;i<s.length();i++){
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i),0)+1);
        }
        int a[] = new int[map.size()];    // 只存放每个字母的个数
        int i = 0, n = a.length;
        Set set = map.entrySet();
        for(Object obj : set){
            Map.Entry<Character, Integer> m = (Map.Entry)obj;
            a[i++] = m.getValue();
        }
        // ************************** 重点：移除字母
        // 每次移除剩余最多的字母，使其剩下的个数比倒数第二多的少1个，直到移除k次
        while(k > 0){
            Arrays.sort(a);           // 排序：找到每次剩余最多的字母的个数
            int t = a[n-1]-a[n-2]+1;  // 每次移除t个
            a[n-1] -= t<=k ? t:k;     // 需要移除的个数满足t<=k，则移除t个；否则只能移除k次
            k -= t;                   // 还可以继续操作k次
        }
        // *****************************************************
        for(i=0;i<n;i++){
            sum += a[i]*a[i];
        }
        System.out.println(sum);
    }
}