蓝桥杯|分糖果（Python）：组成的字符串中字典序最大的字符串最小

这篇文章介绍了蓝桥杯|分糖果（Python）：组成的字符串中字典序最大的字符串最小，分享给大家做个参考，收藏Python资料网收获更多编程知识

 1.问题描述：

最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了n个不同种类的糖果，用小写的阿拉伯字母表示。
每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串s[团的字典序。
肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的max(s[1],s[2], s[3],…, s[a])。

2.代码：

#输入糖果个数n,人数x,并排序存放数组中：
n,x=map(int,input().split())
candy=input()
candies=sorted(candy)
#分为三种情况：
#第一：所有糖果都一样，即字符串只有一种字符：
if candies[0]==candies[n-1]:
    print(candies[0]*(n//x)+(candies[0] if n%x!=0 else''))
    #(theone if count[theone] % x != 0 else '')
    # for i in range(n//x+(n%x!=0)):
    #     print(candies[i],end='')
#第二：糖果不完全相同且前x个糖果完全相同，即第一种糖果（字符）>=x,第一个糖果每个人至少有一个：
elif candies[0]==candies[x-1]:
    #假设最后一个人为最大字符串，即后面所有糖果都分给最后一个人
    for i in range(x-1,n):
        print(candies[i],end='')
#第三：糖果不完全相同且前x个糖果也不完全相同：
else:
    #假设最后一个人为最大字符串，即最后一个人分到的第一个糖果为最大，其余糖果分给其他人：
    print(candies[x-1])

3.题目解析：

（1）不同糖果对应不同的字符；

（2）“使得所有糖果组成的字符串中字典序最大的字符串尽可能小。请输出能够实现字典序最小可能的max(s[1],s[2], s[3],…, s[a])”：字符串有多种分配方式组成不同的(s[1],s[2], s[3],…, s[a])，其中字典序最大的字符串s[n-1]（代码中第二三种情况假设为最后一个字符串），要满足最小的可能;

（3）字典序大小就是按ASCII编码大小进行比较的：例如，a<b,ab<abc

4.三种情况解释：

第一种情况：若n正好整除x则平均分，若有余数，剩余的不足再分给每个人，但是最后一个字符串必须被分到一个，且只能分一个。例如，输入：5 3 aaaaa，输出：aa

第二种情况：不完全相同且前x个糖果完全相同，即第一种糖果（字符）>=x,第一个糖果可以分一轮。后面剩余的字符都分给最后一个字符串，保证其最大字符串的最小可能。例如输入：6 3 aaaabc，输出：aabc

第三种情况：糖果不完全相同且前x个糖果也不完全相同，即第一种糖果<3不足够分一轮。那么第一轮分给最后一个人满足字符串字典序最大，剩余的无须再分给最后一个人，否则不满足最小可能。例如输入：5 3 aabcd 输出：b

版权声明：本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：jacktools123@163.com进行投诉反馈，一经查实，立即删除！