有一种有趣的字符串价值计算方式:统计字符串中每种字符出现的次数,然后求所有字符次数的平方和作为字符串的价值
例如: 字符串"abacaba",里面包括4个'a',2个'b',1个'c',于是这个字符串的价值为4 * 4 + 2 * 2 + 1 * 1 = 21
牛牛有一个字符串s,并且允许你从s中移除最多k个字符,你的目标是让得到的字符串的价值最小。
输入包括两行,第一行一个字符串s,字符串s的长度length(1 ≤ length ≤ 50),其中只包含小写字母('a'-'z')。 第二行包含一个整数k(0 ≤ k ≤ length),即允许移除的字符个数。
输出一个整数,表示得到的最小价值
aba 1
2
思路:
先计算每个字母出现次数,然后每次减出现次数最高的那个,注意:没减一次最大值会变化。
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String inputString = scanner.nextLine(); int k = scanner.nextInt(); scanner.close(); // 记录每个元素出现次数 int[] numArray = new int[26]; for (int i = 0; i < inputString.length(); i++) { numArray[inputString.charAt(i) - 'a']++; } // 按照出现次数进行排序 Arrays.sort(numArray); for (int i = numArray.length - 1; i >= 1; i--) { // 该值必须大于后面的值,加上下面的排序保证每次都是减出现次数最多的那个位置值 while (numArray[i] > 0 && numArray[i] >= numArray[i - 1] && k > 0) { numArray[i]--; k--; // 每次减完排序,一直减最大的那个 Arrays.sort(numArray); } } long sum = 0; for (int i = 0; i < numArray.length; i++) { sum += numArray[i] * numArray[i]; } System.out.println(sum); } }
#include<iostream> #include<string> #include<map> #include<queue> #include<utility> #include<cmath> using namespace std; class Solution { public: /**********************************字符串价值********************************************/ void returnMinValue() { string str; cin >> str; map<string, int> dir; while (!str.empty()) { ++dir[str.substr(0, 1)]; str.erase(0, 1); } priority_queue<pair<int, string>> pque; for (auto begin = dir.begin(); begin != dir.end();++begin) pque.push(make_pair((*begin).second, (*begin).first)); int k = 0; cin >> k; int res = 0; while (!pque.empty()) { pair<int, string> curr = pque.top(); pque.pop(); int dif = curr.first - pque.top().first; if (dif >= k) { res += pow((curr.first - k), 2); while (!pque.empty()) { res += pow((pque.top().first), 2); pque.pop(); } cout << res << endl; return; } else { curr.first -= (dif + 1); k -= (dif + 1); pque.push(curr); } } } }; int main() { Solution s3; s3.returnMinValue(); system("pause"); return 0; }
#include <iostream> #include <string> #include <algorithm> #include <vector> int main() { std::string input(""); std::cin >> input; int k = 0; std::cin >> k; int arr[26] = {0}; for (int i = 0; i < input.length(); i++) { arr[input.at(i) - 'a'] += 1; } std::vector<int> sort_arr; for (int i = 0; i < 26; i++) { if (arr[i] > 0) sort_arr.push_back(arr[i]); } int t = 0; std::sort(sort_arr.begin(), sort_arr.end()); int max_site = sort_arr.size() - 1; int second_site = max_site; while(k > 0) { /* 最小的价值不是让最大的数减k,而是让各个数尽量小 首先要让最大的数减到和第二大的数一样,然后再将第一和第二大的数减到和第三大的数一样 如果所有数都一样,再依次减一 直到K用尽 */ if (sort_arr[max_site] == sort_arr[second_site]) { if (second_site >= 0) { int t = second_site; for (int i = second_site; i >= 0; i--) { if (sort_arr[i] < sort_arr[second_site]) { t = i; break; } } second_site = t < second_site ? t : -1; } } for (int i = sort_arr.size() - 1; i > second_site && k > 0; i--) { sort_arr[i] -= 1; k -= 1; } } int64_t value = 0; for (int i = 0; i < sort_arr.size(); i++) { value += (sort_arr[i] * sort_arr[i]); } std::cout << value << std::endl; return 0; }
s = str(input()) k = int(input()) d = {} for c in set(s): d[c] = s.count(c) nums = list(d.values()) minus = 0 while minus < k: nums.sort(reverse=True) nums[0]-=1 minus+=1 print(sum([n**2 for n in nums]))
import java.util.*; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int k = sc.nextInt(); sc.close(); int[] nums = new int[26]; int res = str.length() - k; if (res < 2) { System.out.println(res); return; } for (int i = 0; i < str.length(); ++i) { nums[str.charAt(i) - 'a']++; } Arrays.sort(nums); int maxIndex = 25,i = 25; res = 0; while (k > 0) { if (maxIndex == 0) { nums[maxIndex] -= k; k = 0; } while (k> 0 && nums[maxIndex] > nums[maxIndex - 1]) { for( i = maxIndex;k>0 &&i<26;++i){ --nums[i]; --k; } } --maxIndex; } for (int j = 0;j<=maxIndex;++j){ res += (int)Math.pow(nums[j], 2); } if(maxIndex<25) { res += (i - maxIndex - 1) * (int) Math.pow(nums[maxIndex + 1], 2); if(i<26) res += (26 - i) * (int) Math.pow(nums[i], 2); } System.out.println(res); } }
#include<iostream> #include<string> #include<map> #include<utility> #include<vector> #include<iterator> #include<cmath> //幂指数的头文件 #include<algorithm> //make_heap头文件 using std::string;using std::map;using std::pair;using std::make_pair;using std::vector; using std::cin;using std::cout;using std::endl;using std::getline;using std::make_heap; map<char,size_t> str_count(const string& str){ //计算string中各char出现的次数,以map形式表示 string::const_iterator iter = str.begin(); map<char,size_t> char_map; while(iter != str.end()){ //插入参考Primer385页 auto ret = char_map.insert(make_pair(*iter,1)); if(!ret.second) ++ret.first->second; ++iter; } return char_map; } vector<size_t> map_2_vec(map<char,size_t>&char_map){ //将上一函数出现的map转变为vector形式,即仅表示string中各字符出现的次数 vector<size_t>vec_count; auto map_iter = char_map.cbegin(); while(map_iter!=char_map.cend()){ vec_count.push_back(map_iter->second); ++map_iter; } char_map.clear(); //删除原始的map,释放空间 //char_map.erase(char_map.begin(), char_map.end()); return vec_count; } int vec_sum(const vector<size_t>& vec_count){ int count = 0; for(auto vec:vec_count){ count += pow(vec,2); } return count; } int main(int argc,char* argv[]){ string str; int change_num; getline(cin,str);cin>>change_num; //读取命令行输入 if(str.empty()||str.size()<=change_num){ //判断输入数据 cout<<0<<endl; return 0; } map<char,size_t>char_map = str_count(str); //统计string中字符出现的关联容器 vector<size_t>vec_count = map_2_vec(char_map); while(change_num){ //对vector构建最大堆,每次将最大的数值减一; make_heap(vec_count.begin(), vec_count.end(), std::less<size_t>()); --vec_count[0]; --change_num; } int count = vec_sum(vec_count); //计算删除后的vec各元素的平方和。 cout<<count<<endl; return 0; }
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader bf = new BufferedReader(new InputStreamReader(System.in)); String str = bf.readLine(); int num = Integer.parseInt(bf.readLine()); int[] array = Delete(str,num); int count=0; for (int a:array){ count+=a*a; } System.out.println(count); } static int[] Delete(String str,int num){ int[] array = new int[26]; for(int i=0;i<str.length();i++){ array[(int)str.charAt(i)-'a']++; } for (int i=0;i<num;i++){ Arrays.sort(array); array[array.length-1]--; } return array; } }
input_str=input() remove_n=int(input()) input_list=[i for i in input_str.strip()] k={} for i in input_list: if i in k: k[i]+=1 else: k[i]=1 list_n=[k[i] for i in k] while remove_n: max_index=list_n.index(max(list_n)) list_n[max_index]-=1 remove_n-=1 s=0 for i in list_n: s+=i*i print(s)
import java.util.*; public class Main{ public static void main(String []args){ Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int k = sc.nextInt(); int[] array = new int[26]; //array[0]代表a出现的次数,后面依次类推 for(int i = 0; i < str.length(); i ++){ char temp = str.charAt(i); int num = temp - 'a'; array[num]++; } //每次array数组中最大的数减一,为了找到最大的数,通过Arrays.sort()进行排序 int count = 0; while(k != count){ Arrays.sort(array); if(array[array.length-1] != 0){ array[array.length-1]--; count ++; } } int sum = 0; //数组的平方和就是最后的结果 for(int j = 0; j < array.length; j ++){ sum += Math.pow(array[j], 2); } System.out.println(sum); return; } }