开发者社区云计算文章正文

CF979B Treasure Hunt（贪心思维）

2022-12-01 111 发布于山东

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： CF979B Treasure Hunt（贪心思维）

linkkkk

题意：

思路：

贪心的考虑，尽可能的将字符串变成出现最多的字母是最优的。

对于每一个字符串记录一下长度和出现最多的字母个数，最大美丽值就是m i n ( 长度，出现最多字母个数 + 操作次数 )

如果仅仅出现了一种字母，仅操作一次的话，最大值就是长度− 1

代码：

#include<bits/stdc++.h>
using namespace std;
string s[4];
int n;
struct node{
  int len,id;
}a[4];
bool cmp(node a,node b){
  return a.len>b.len;
}
int cul(string s){
  int cnt=0,len=s.size();
  map<int,int>mp;
  for(int i=0;s[i];i++){
    mp[s[i]]++;
    cnt=max(cnt,mp[s[i]]);
  }
  if(mp.size()==1&&n==1) return len-1;
  return min(len,cnt+n);
}
string name[]={"","Kuro","Shiro","Katie"};
int main(){
  cin>>n;
  for(int i=1;i<=3;i++){
    cin>>s[i];
    a[i].len=cul(s[i]);
    a[i].id=i;
  }
  sort(a+1,a+1+3,cmp);
  if(a[1].len!=a[2].len) cout<<name[a[1].id]<<endl;
  else cout<<"Draw";
  return 0;
}