1 条题解

  • 0
    @ 2024-6-12 15:24:22

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

    暴力部分

    n20n\leq 20:直接每次dfsdfs合成一段,看看合成kk段以后的代价。

    n500n\leq 500dpi,jdp_{i,j}表示前ii个位置合成了jj段的最小代价。

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

    正解

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

    #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;
    }
    

    信息

    ID
    1422
    时间
    1000ms
    内存
    256MiB
    难度
    7
    标签
    (无)
    递交数
    116
    已通过
    28
    上传者