分糖果
问题描述
最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了 个不同种类的糖果，用小写的阿拉伯字母表示。每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串 的字典序。肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。
请输出能够实现字典序最小可能的max 。
样例输入
6 2
caabdc
样例输出
abccd
代码
n, x = map(int, input().split()) s = sorted(input()) if s[0] != s[x - 1]: print(s[x - 1]) elif s[x] == s[-1]: print(''.join(s[0::x])) else: print(''.join(s[x - 1:]))
最小化战斗力差距
问题描述
小蓝是机甲战队的队长，他手下共有 名队员，每名队员都有一个战斗力值 。现在他需要将这 名队友分成两组 和 ，分组必须满足以下条件：
- 每个队友都属于a 组或b 组。
- a组和 b组都不为空。
- 战斗力差距最小。
样例输入
3
1 2 3
样例输出
1
代码
n = int(input()) a = sorted(map(int, input().split())) print(min(a[i] - a[i - 1] for i in range(1, n)))
小蓝的零花钱
问题描述
小蓝和小桥正在玩一个游戏，他们有一个长度为 的序列，其中既有偶数也有奇数，且偶数和奇数的数量相等。小蓝有一些零花钱，他可以用这些钱来做一个特殊的操作：他在序列中选取一个位置，然后在这个位置上将序列分成两段，要求每一段中偶数和奇数的数量都相等。小蓝想要用他的零花钱尽可能多地进行这个操作，但每次操作都需要花费代价。具体而言，每次选取的位置可以看成是对序列进行切割，切割需要花费的代价为切割两端的元素的差的绝对值。小蓝想知道，在他的预算范围内，最多能进行多少次操作。
请你帮助小蓝计算最多可以进行的操作次数。
样例输入
6 3
1 2 3 4 5 6
样例输出
2
代码
n, m = map(int, input().split()) a = list(map(int, input().split())) cnt = 0 pos_l = [] for i in range(n - 1): cnt += 1 if a[i] % 2 else -1 if cnt == 0: pos_l.append(i) s = sorted(abs(a[i] - a[i + 1]) for i in pos_l) ans = 0 for i in s: if m - i < 0: break m -= i ans += 1 print(ans)
希尔排序模板题
问题描述
希尔排序是直接插入排序算法的一种更高效的改进版本，但它是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出的改进方法之一：
1. 插入排序在对几乎已经排好序的数据操作时，效果是非常好的。
2. 插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位。
而通常对于希尔排序中我们选择增量序列为： ，其中 为待排序数组的长度。
现在，给你一个整数数组，要求使用希尔排序算法对它进行排序。
样例输入
5
5 2 9 1 5
样例输出
1 2 5 5 9
代码
def shell_sort(a, steps): for step in steps: for i in range(step, len(a)): for j in range(i, step - 1, -step): if a[j] < a[j - step]: a[j], a[j - step] = a[j - step], a[j] else: break n = int(input()) a = list(map(int, input().split())) steps = [n // (1 << i) for i in range(n.bit_length())] shell_sort(a, steps) print(*a)
