思路描述
先对牛棚的编号求一个差分数组,代表有牛住的牛棚之间隔了多少个无牛住的牛棚。我们实质上就是选m-1个间隔最大的牛棚相互独立,其他的牛棚都可以合并到这几个牛棚或者不合并。换句话说就是想要分出m个区间就要在这些牛棚中放m-1个隔板。
证明及相关操作
- 要使得板子的总长度最小,那肯定要用上m个长度任意的板子,如果板子的数量大于有牛住的牛棚的数量那么最好是对每个这些棚子放一个板子。
- 用排序去选择$min(c, m-1)$个最大间隔的牛棚。
- 将间隔大的牛棚的值都改成1,求差分数组的总和便是答案。
具体细节参考代码。
Python参考代码
m, s, c = map(int, input().split())
a = [0] + sorted(int(input()) for _ in range(c))
diff = [0] * 201
for i in range(1, c+1):
diff[i] = a[i] - a[i-1]
diff[1] = 1
diff.sort(reverse=True)
for i in range(min(m-1, c)):
diff[i] = 1
print(sum(diff))