[USACO 2016 Jan S]Angry Cows
这题用到二分答案
思路为二分判断minposi-maxposi之间的r是否符合要求

  • 二分答案解法需要答案具有单调性, 如在一段区间内使得xx的最大值最小
  • 此时更大的答案/更小的答案总是符合要求, 而需要找到符合要求的临界值
  • 运用这种解法, 可以将问题的已知和未知转化

vec一个个弹出超时, 换成int[]没注意细节, 含泪改了半个小时, 换用数据结构的时候一定记得关注细节啊!

//hay bales??
//愤怒的小鸟
//if(n<=k) return 1;
//已知炸弹个数与障碍物坐标
//求最小炸弹威力

//考虑平均情况下最大炸弹需要炸掉的个数, 取最差情况时的半径
//if(n%k)(n-k)/k+1, 个数为n%k
//else (n-k)/k, 个数为n%k
//等一下, 这个策略对吗?不对 1 2 3 4 5 99 165  k = 3 r = 2
//再想想
//动规?

//这题用到二分答案
//思路为二分判断minposi-maxposi之间的r是否符合要求
//二分答案解法需要答案具有单调性, 如在一段区间内使得xx的最大值最小
//此时更大的答案/更小的答案总是符合要求, 而需要找到符合要求的临界值
//运用这种解法, 可以将问题的已知和未知转化

//vec一个个弹出超时, 换成int[]没注意细节, 含泪改了半个小时

#include <bits/stdc++.h>
using namespace std;
int n, k;
int pos[50005];//用vec应该也行
bool check(int r)//已知r, 问需求炸弹个数
{
    //这个怎么求呢
    //456 500 501 502 503 999 5645 r = 2 num = 4
    //贪心?
    int nownum = 0, left, right, nowposi = 0;
    while(nowposi<n)
    {
        nownum++;
        left = pos[nowposi];
        right = left+2*r;
        nowposi = upper_bound(pos, pos+n, right) - pos;
        //pos.erase(pos.begin(), upper_bound(pos.begin(), pos.end(), right));
    }
    if(nownum<=k) return true;
    else return false;
}

int main()
{
    
    cin>>n>>k;
    if(n<=k) 
    {
        cout<<1;
        return 0;
    }
    for(int i = 0; i<n; i++)
    {
        cin>>pos[i];
    }
    sort(pos, pos+n);// 2 5 9 45 79 79-2 = 77 77/2 = 38.5
    int i = 1, j = (pos[n-1] - pos[0]+1)/2, mid;
    while(i<j)//找第一个大于等于临界值的数
    {
        mid = (i+j)/2;
        if(check(mid))
        {
            j = mid;
        }
        else
        {
            i = mid+1;
        }
    }
    cout<<i;
    return 0;
}