Angry Cows(Silver)

Angry Cows(Silver)

• 前言

  大菜鸡看错题了QwQ

• 分析

  1. 大水题(我是怎么把他看成单调队列优化dp的？)
  2. 如果想要把所有的草堆点燃，那么我们就不能多浪费一米，即从左边开始圈,也就是说，如果点 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;
}