?分糖果
问题描述
最近暑期特训算法班的同学们表现出色，他们的老师肖恩决定给他们分发糖果。肖恩购买了 个不同种类的糖果，用小写的阿拉伯字母表示。每个糖果必须分发给一个同学，并且每个同学至少要分到一个糖果。同学们的开心程度定义为他们所分到的糖果组成的字符串 的字典序。肖恩希望同学们的开心程度相差尽量小，因此他要找到一种方案，使得所有糖果组成的字符串中字典序最大的字符串尽可能小。
请输出能够实现字典序最小可能的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)?