给你n张卡片，卡片上仅包含大写英文字母，现你可从这n张卡片中选出k张，要求得到尽可能高的分数。
关于分数的计算方式，在你所选择的k张卡片中，含有相同字母的卡片分数为卡片数乘以相同卡片个数。
就样例而言，选择九张D和其他任意一张，得到的结果为9*9+1 。
[编程题]字母卡片
#include <bits/stdc++.h>
using namespace std;
int main()
{
long long n,m;
while(cin>>n>>m)
{
string str;
cin>>str;
vector<long long> v(26,0);
for(int i = 0;i<n;i++)
v[str[i]-'A']++;
sort(v.begin(), v.end());
long long k = 25,ans = 0;
while(m>0)
{
if(m>=v[k])
{
ans+=v[k]*v[k];
m=m-v[k];
k--;
}
else
{
ans+=m*m;
break;
}
}
cout<<ans<<endl;
}
return 0;
}
发表于 2019-07-12 19:20:55
回复(0)
/*谜之题意+多组输入从来不提醒一下的- - 。*/
#include <bits/stdc++.h>
#define LL long long
using namespace std ;
int main(){
LL a[30] ;
string s ;
int n , k ;
while( cin >> n >> k ){
cin >> s ;
memset( a , 0 , sizeof(a) ) ;
for( int i = 0 ; i < n ; i++ ){
a[(int)s[i]-'A'] ++ ;
}
sort( a , a + 26 ) ;
LL res = 0 ;
for( int i = 25 ; i >= 0 ; i-- ){
LL v = min( (LL)k , a[i] ) ;
res += v * v ;
k -= v ;
}
cout << res << endl ;
}
return 0 ;
}
发表于 2020-02-11 16:50:59
回复(2)
直接对n张卡片的每个字母进行计数，按计数进行降序排列，然后顺序去凑k张卡片就可以了。
from collections import defaultdict while 1: try: n, k = map(int, input().strip().split()) cards = list(input().strip()) counter = defaultdict(lambda: 0) # 对每个字母进行计数 for card in cards: counter[card] += 1 # 每个字母按计数降序排列 counter_new = sorted(counter.items(), key=lambda x: -x[1]) score = 0 for alpha, count in counter_new: if count < k: # 此时字母有count张，还未凑满k张，分数直接+count**2 score += count**2 k -= count else: # 此时字母无法利用全部的count张牌加分，分数只能+k**2 print(score + k**2) break except: break
发表于 2021-01-31 11:02:47
回复(0)
JAVA思路：
首先遍历字符串，用HashMap存值，key是字符，value是次数。
因为本题不关注最后是什么字母，只需把values值摘出来，从大到小排序。
遍历排序后的数组或集合，直到达到k，返回一个long的结果
需要注意的点是结果是long时要对int强转
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
public class Main {
static Scanner sc = new Scanner(System.in);
public static void main(String[] args) {
while (sc.hasNext()) {
//获取输入数据
String[] str0 = sc.nextLine().split(" ");
int n = Integer.parseInt(str0[0]);
int k = Integer.parseInt(str0[1]);
String str = sc.nextLine();
//处理输入数据->键值对
int len = str.length();
HashMap<Character, Integer> map = new HashMap<Character, Integer>();
for (int i = 0; i < len ; i++) {
char ch=str.charAt(i);
if(map.containsKey(ch)) {
map.put(ch, map.get(ch)+1);
}else {
map.put(ch, 1);
}
}
//对值排序
ArrayList<Integer> list = new ArrayList<Integer>(map.values());
long grade = 0;
// Collections.sort(list);
// Collections.reverse(list);
Collections.sort(list,new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// TODO Auto-generated method stub
return o2-o1;
}
});
//计算结果
for (int i : list) {
if (i >= k) {
grade += (long) k * k;
System.out.println(grade);
break;
} else {
grade += (long) i * i;
k -= i;
}
}
}
}
}
编辑于 2020-07-28 15:58:24
回复(0)
# coding: utf-8
while True:
try:
n, k = list(map(int, input().strip().split(' ')))
cards = input()
c_c = {}
for card in cards:
if card in c_c.keys():
c_c[card] += 1
else:
c_c[card] = 1
values = list(c_c.values())
values.sort()
values.reverse()
result = 0
for value in values:
if k >= value:
result += value**2
k -= value
else:
result += k**2
break
print(result)
except:
break
发表于 2019-09-04 14:21:43
回复(0)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool cmp(int a, int b){
return a>b;
}
int main(){
ll n,k,sum=0;
string s;
while(cin>>n>>k){
ll sum = 0;
cin>>s;
ll a[26];
memset(a,0,sizeof(a));
for(int i=0;i<n;i++){
a[s[i]-'A']++;
}
sort(a,a+26,cmp);
int t=0;
while(k){
if(k>=a[t]){
sum += a[t]*a[t];
k -= a[t];
}else{
sum += k*k;
k = 0;
}
t++;
}
cout<<sum<<endl;
}
return 0;
}
发表于 2019-09-02 09:55:55
回复(0)
import java.util.*;
public class Main {
public void calcu(long k, int n, String s){
//使用HashMap
Map<Character,Integer> map = new TreeMap<Character,Integer>();
int len=0;
for(int i=0;i<s.length();i++)
{
// 如果包含该键值对，值+1
if(map.containsKey(s.charAt(i))){
int num=map.get(s.charAt(i))+1;
map.remove(s.charAt(i));
map.put(s.charAt(i), num);
}else{
//如果不包含，创建新键值对
map.put(s.charAt(i), 1);
len++;
}
}
int []b = new int [len];
int t=0; //用来下标滑动
int ex=0;
long max=0;
//遍历HashMap,将值存进数组
for(Character key : map.keySet()){
int num =map.get(key);
b[t]=num;
++;
}
//对数组排序,冒泡
for(int i=0;i<len;i++){
for(int j=0;j<len-i-1;j++){
if(b[j]>b[j+1]){
ex=b[j];
b[j]=b[j+1];
b[j+1]=ex;
}
}
}
//选值
for(int i=len-1;i>=0;i--){
if(b[i]>=k){
max = max+k*k;
System.out.println(max);
break;
}else{
max = max+b[i]*b[i];
k = k-b[i];
}
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Main m = new Main();
while(sc.hasNext())
{
int n = sc.nextInt();
long k = sc.nextLong();
String s= sc.next();
m.calcu(k, n, s);
}
}
}
编辑于 2019-08-16 15:14:46
回复(3)
#include<iostream>
#include<string>
#include<algorithm>
int main()
{
long long n,k;
std::string s;
while(std::cin>>n>>k)
{
std::cin>>s;
long long a[26]={0};
for(long long i=0;i<n;i++)a[s[i]-'A']++;
std::sort(a,a+26);
long long count=0;
for(int j=25;j>=0;j--)
{
if(a[j]>=k)
{
count+=k*k;
std::cout<<count<<std::endl;
break;
}
else
{
count+=a[j]*a[j];
k-=a[j];
}
}
}
return 0;
}
#include<string>
#include<algorithm>
int main()
{
long long n,k;
std::string s;
while(std::cin>>n>>k)
{
std::cin>>s;
long long a[26]={0};
for(long long i=0;i<n;i++)a[s[i]-'A']++;
std::sort(a,a+26);
long long count=0;
for(int j=25;j>=0;j--)
{
if(a[j]>=k)
{
count+=k*k;
std::cout<<count<<std::endl;
break;
}
else
{
count+=a[j]*a[j];
k-=a[j];
}
}
}
return 0;
}
发表于 2020-09-10 23:42:06
回复(0)
#include <stdio.h>
int n;
int main(){
while(scanf("%d",&n)!=EOF)
{
char a[n];
int b[n];
int i,k,tmp=0;
scanf("%d",&k);
scanf("%s",a);
for(int i=0;i<n;i++){
a[i]=(a[i]-'A');
}//转为数字
int x,y,z=0;
for(int z=(n-1);z>0;z--){
for(x=0;x<z;x++){
y=(x+1);
if(a[x]>a[y]){
tmp=a[x];
a[x]=a[y];
a[y]=tmp;
}
}
}//排序
int count=1;
for(z=0;z<n-1;z++){
x=z;
y=(z+1);
b[z]=0;
if(a[x]==a[y]){
count++;
b[z]=0;
}
else {
b[z]=count;
count=1;
}
if(z==(n-2)){
b[z]=count;
b[n-1]=0;
}
}//数相同的个数，保存到数组b
for(int z=(n-1);z>0;z--){
for(x=0;x<z;x++){
y=(x+1);
if(b[x]>b[y]){
tmp=b[x];
b[x]=b[y];
b[y]=tmp;
}
}
}//数组b排序
int res=0;
for(z=(n-1);k>0;z--){
if(k>b[z]){
res=(res+(b[z]*b[z]));
k=(k-b[z]);
}
else {
res=(res+(k*k));
k=0;
}
}//取牌，计算
printf("%d\n",res);
}
} C语言的，可惜超时了
发表于 2020-08-12 01:31:31
回复(0)
///
/// 存入字典，然后对key值排序，然后输出结果。例子里面用long long着实是来恶心人的
///
#include<iostream>
#include<map>#include<algorithm>
#include<vector>
using namespace std;
int main()
{
int cnt,tar;
while(cin>>cnt>>tar)
{
map<char,int> dict;
char c;
for(int i=0;i<cnt;i++)
{
cin>>c;
if(dict.find(c)!=dict.end())
{
dict[c] += 1;
}
else
{
dict[c] = 1;
}
}
vector<pair<char,long long>> sorted;
for(auto iter=dict.begin();iter!=dict.end();iter++)
{
sorted.push_back(make_pair(iter->first,iter->second));
}
sort(sorted.begin(),sorted.end(),[](const auto &l,const auto &r)
{
return l.second>r.second;
}) ;
long long counted = 0;
long long sum = 0;
for(long long k=0;k<sorted.size();k++)
{
//cout<<sorted[k].first<<sorted[k].second<<endl;
if(counted+sorted[k].second>tar)
{
// more than can hold
sum += (tar-counted)*(tar-counted);
break;
}
sum += sorted[k].second*sorted[k].second;
counted+=sorted[k].second;
}
cout<<sum<<endl;
}
return 0;
}
发表于 2020-08-08 14:08:22
回复(0)
from collections import Counter import sys lines = [line for line in sys.stdin] for i in range(0, len(lines), 2): n, k = map(int, list(lines[i].split())) cards = lines[i + 1] cnt = Counter(cards) cnt = sorted(cnt.values()) res = 0 while k > 0: cur = min(cnt.pop(), k) k -= cur res += cur*cur print(res)
发表于 2020-08-05 23:25:29
回复(0)
import java.util.*;
public class Main
{
public static void main(String[] args)
{
Scanner in = new Scanner(System.in);
int n, k;
while (in.hasNextInt())
{
n = in.nextInt();
k = in.nextInt();
in.nextLine();
String s = in.nextLine();
Map<Character, Integer> map = new HashMap<>();
for (char c : s.toCharArray())
{
int count = map.getOrDefault(c, 0);
map.put(c, count + 1);
}
Queue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);
for (char c : map.keySet())
{
pq.offer(map.get(c));
}
long ans = 0;
while (!pq.isEmpty())
{
if (k == 0) break;
int num = Math.min(k, pq.poll());
k -= num;
ans += (long)num * num;
}
System.out.println(ans);
}
}
}
发表于 2020-07-31 20:03:42
回复(0)
import sys if __name__=="__main__": lines = sys.stdin.readlines() while lines: [n, k] = list(map(int, lines.pop(0).strip().split())) nums = lines.pop(0).strip() from collections import Counter a = dict(Counter(nums)) A = sorted(dict(Counter(nums)).values()) if k <= A[-1]: print(k*k) else: A = A[::-1] res = 0 while k > A[0]: res += A[0]*A[0] k -= A[0] A.pop(0) res += k*k print(res)
题目没有说一次给出多个样例啊，感觉这个还是得讲出来吧。
发表于 2020-06-08 20:42:37
回复(0)
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,k;
while(cin>>n>>k)
{
string s;
cin>>s;
map<char,int>mp;
for(char c:s)
mp[c]+=1;
vector<long long>v;
for(auto t:mp)
v.push_back(t.second);
sort(v.rbegin(),v.rend());
// 注意数据类型 有坑 int要溢出的
long long score = 0;
for(int i=0;i<v.size();++i){
if(k==0) break;
if(k>=v[i]) {
score+=v[i]*v[i];
k-=v[i];
}
else {
score+=k*k;
k = 0;
}
}
cout<<score<<endl;
}
return 0;
}
发表于 2020-06-06 16:27:48
回复(0)
/*
可以通过测试用例，提交的时候请检查是否存在数组越界等非法访问情况，
求大佬帮忙看看
*/
import java.util.Scanner;
import java.util.HashMap;
import java.util.Arrays;
public class Main{
public static void main(String[] args){
Scanner in=new Scanner(System.in);
long n=in.nextLong();
long k=in.nextLong();
String a=in.next();
char []b=a.toCharArray();
HashMap<Character,Integer> map=new HashMap<>();
HashMap<Integer,Character> mapkey=new HashMap<>();
for(int i=0;i<b.length;i++){
if(map.containsKey(b[i])!=true)
{map.put(b[i],0);
mapkey.put(i,b[i]);}
}
long [] c =new long [map.size()];
for(int i=0;i<map.size();i++){
long count =0;
for(int j=0;j<b.length;j++){
if(mapkey.get(i).equals(b[j])){
count++;
}
}
c[i]=count;
}
Arrays.sort(c);
long num=0;
for(int i=c.length-1;i>=0;i--){
if(k>=c[i])
{num=c[i]*c[i];
k=k-c[i];}
else{
num=num+k*k;break;
}
}
System.out.println(num);
}
}
发表于 2020-05-06 16:47:00
回复(0)
题目描述得很奇怪，“含有相同字母的卡片分数为卡片数乘以相同卡片个数”，不知道这个“卡片数”是指总卡片数还是当前字母的卡片数，有歧义，根据大家对题目的理解写了答案：
import java.util.*;
public class Main {
private static void deal(int n, int k, String str) {
int[] arr = new int[26];
for (int i = 0; i < n; i++) {
int idx = str.charAt(i) - 'A';
arr[idx]++;
}
Arrays.sort(arr);
int idx = 25;
long res = 0L;;
while (k >= 1 && idx >= 0) {
if (k >= arr[idx]) {
res += (long)arr[idx] * (long)arr[idx];
k -= arr[idx];
} else {
res += (long)k * (long)k;
k = 0;
}
idx--;
}
System.out.println(res);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
int n = sc.nextInt();
int k = sc.nextInt();
String str = sc.next();
deal(n, k, str);
}
}
}
编辑于 2020-04-16 13:14:35
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Card[] cards;
while (sc.hasNext()) {
int n = sc.nextInt();//卡片总数
int k = sc.nextInt();//选出的卡片数
char[] cardsArray = new char[n];
String s = sc.next();
for (int a = 0; a < n; a++) {
cardsArray[a] = s.charAt(a);
}
long score = 0;
Map<Character, Long> map = new HashMap<>();
for (char c : cardsArray) {
map.put(c, map.getOrDefault(c, 0L) + 1);
}
cards = new Card[map.size()];
int j = 0;
for (char c : map.keySet()) {
cards[j++] = new Card(c, map.get(c));
}
Arrays.sort(cards, new CardComparator());
for (int i = 0; i < map.size(); i++) {
long num = cards[i].times;
if (num <= k) {
score += num * num;
k -= num;
}
}
System.out.println(score + k*k);
}
}
}
class Card {
public char letter;
public long times;
public Card(char letter, long times) {
this.letter = letter;
this.times = times;
}
}
class CardComparator implements Comparator<Card> {
@Override
public int compare(Card o1, Card o2) {
return Long.compare(o2.times, o1.times);
}
}
发表于 2020-04-05 03:01:43
回复(0)
我的代码有问题，有一个样例没有通过，求问我的哪里出错了？我自己检查一直没找出来。
#include<bits/stdc++.h>
using namespace std;
bool cmp(int a, int b){
return a > b;
}
int main(){
int n, k;
while(cin >> n >> k){
long long cnt[26] = {0};
//char ch;
string s;
cin >> s;
//cout << n << ' ' << s.size() << endl;
n = n > s.size()? s.size(): n;
k = k > n? n: k;
for(int i = 0; i < n; i++){
//cin >> ch;
cnt[s[i] - 'A']++;
}
sort(cnt, cnt + 26, cmp);
long long curk = 0;
long long sum = 0;
long long last = k - curk;
while(last > 0){
for(int i = 0; i < 26; i++){
last = k - curk;
int num = cnt[i] > last? last: cnt[i];
sum = sum + num * num;
curk = curk + num;
}}
cout << sum << endl;}
return 0;
}
发表于 2019-09-21 13:25:31
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
