显然最后是值相邻的一段合成了一瓶。

暴力部分

$n\leq 20$：直接每次$dfs$合成一段，看看合成$k$段以后的代价。

$n\leq 500$：$dp_{i,j}$表示前$i$个位置合成了$j$段的最小代价。

$k=2$：暴力枚举分割位置即可。

正解

二分答案，然后从左往右贪心，看看是否用不超过$k$段就能完成任务即可。

#include<bits/stdc++.h>
#define ll long long
#define maxn 100005
using namespace std;
int n,k,a[maxn];
int check(int lim)
{
	int num=0;
	for (int l=1,r=1;l<=n;l=r+1,r=l)
	{
		while (r<n && a[r+1]-lim<=a[l]+lim) r++;
		num++;
	}
	return num<=k;
}
int main()
{
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	sort(a+1,a+n+1);
	int now=0;
	for (int step=1<<30;step>=1;step=step>>1)
	if (check(now+step)==0)
		now+=step;
	cout<<now+1<<endl;
}