[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;
}