前言
大菜鸡看错题了QwQ
分析
- 大水题(我是怎么把他看成单调队列优化dp的?)
- 如果想要把所有的草堆点燃,那么我们就不能多浪费一米,即从左边开始圈,也就是说,如果点 i 还没有被点燃,那么一定得在这里降落一个,因为长度为R,所以能引爆的区域就是[a[i]-R,a[i]+R]
代码
//#pragma GCC optimize(3,"inline","Ofast","fast-math","no-stack-protector","unroll-loops") //#pragma GCC target("sse","sse2","sse3","sse4","avx","avx2","popcnt") #include<bits/stdc++.h> #define dl double #define R register #define ll long long #define inf INT_MAX using namespace std; const int N=5e4+10; const dl eps=1e-3; int n,k; int a[N]; inline bool check(int li) { int sum=0,now=-1e9; for (int i=1;i<=n;i++) { if(now<a[i]-li) { now=a[i]+li; sum++; if(sum>k) return 0; } } return 1; } int main() { scanf("%d%d",&n,&k); for (int i=1;i<=n;i++) scanf("%d",&a[i]); sort(a+1,a+n+1); int l=0,r=a[n],ans; while(l<=r) { int mid=(l+r)/2; if(check(mid)) r=mid-1,ans=mid; else l=mid+1; } printf("%d\n",ans); return 0; }