二分答案
顺便问下爆搜怎么n^2(
by Scene @ 2024-04-21 16:54:30
二分
by ChaosOrb @ 2024-04-21 16:54:58
@[Scene](/user/574338) 两个循环嵌套不会吗？
by Jared0503 @ 2024-04-21 16:58:44
@[ChaosOrb](/user/366942) 有没有时间给一下示例代码呢？
by Jared0503 @ 2024-04-21 17:06:50
@[Jared0503](/user/1074812) 我寻思两个循环嵌套也不是暴搜啊
by TheShuMo @ 2024-04-21 18:07:08
@[Jared0503](/user/1074812)
```
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,l,r) for(register int i=l;i<=r;++i)
const int N=1e5+10;
int n,m,a[N];
bool chk(int mid){
int cnt=0,ls=a[1];
rep(i,2,n-1){
if(a[i]-a[i-1]>mid) return 0;
if(a[i]-ls>mid) ls=a[i-1],++cnt;
}
if(cnt>m-2||(cnt==m-2&&a[n]-ls>mid)||(cnt<m-2&&a[n]-a[n-1]>mid)) return 0;
return 1;
}
signed main(){
ios::sync_with_stdio(false);
cin>>n>>m;
rep(i,1,n) cin>>a[i];
sort(a+1,a+n+1);
int l=0,r=1e9,ans=0;
while(l<=r){
int mid=(l+r)>>1;
if(chk(mid)) ans=mid,r=mid-1;
else l=mid+1;
}
cout<<ans<<"\n";
return 0;
}
/*
5 3
1 2 12 16 20
*/
```
不保证正确性。
by 轩大虾22 @ 2024-04-22 12:00:00
@[轩大虾22](/user/502788) 谢谢
by Jared0503 @ 2024-04-23 21:37:02