题解 P6174 【[USACO16JAN]Angry Cows S】

Velix · 2020-03-11 19:59:28 · 题解

一道较为简单的二分答案题。

将R作为二分的数去检查，然后进行枚举。

可以想到，如果这个数不在上一个炸弹的覆盖范围，那它一定在新炸弹的最左端。程序也就呼之欲出了。

Code

#include<bits/stdc++.h>
using namespace std;
int a[50001],b,c,d,l,r=1000000001,m;
bool check(int x)
{
    int y=0,z=0;
    for(int i=1;i<=b;i++)
        if(z<a[i])y++,z=a[i]+x*2;
    return y<=c;
}
int main()
{
    cin>>b>>c;
    for(int i=1;i<=b;i++)scanf("%d",&a[i]);
    sort(a+1,a+b+1);
    while(l<=r)
    {
        m=l+r>>1;
        if(check(m))r=m-1,d=m;
        else l=m+1;
    }
    cout<<d;
}