bzoj4525[Usaco2016 Jan]Angry Cows

bzoj4525[Usaco2016 Jan]Angry Cows

题意：

有N个草堆在数轴的不同位置，向坐标x处扔炸弹，[x−R,x+R]的草堆都会燃爆。 K个炸弹，问如果要引爆所有的草堆最小的R。草堆数最多50000，坐标最大为10⁹

题解：

二分R，判定时从小到大枚举草堆，如果这个草堆没被炸就在这里放炸弹（实际上是放在此处坐标+R的位置），炸掉与它距离≤2R的草堆，重复上述操作。本弱一开始以为炸掉的是与它距离≤2R+1的草堆，调了0.5hQAQ

代码：

1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define inc(i,j,k) for(int i=j;i<=k;i++) 5 #define INF 0x3fffffff 6 using namespace std; 7 8 int n,k,x[60000]; 9 int main(){ 10 scanf("%d%d",&n,&k); inc(i,1,n)scanf("%d",&x[i]); sort(x+1,x+n+1); 11 int l=0,r=x[n],ans; 12 while(l<=r){ 13 int mid=(l+r)>>1,pre=-INF,tot=0; bool f=0; 14 inc(i,1,n){ 15 if(x[i]-pre>2*mid)tot++,pre=x[i]; 16 if(tot>k){f=1; break;} 17 } 18 if(!f)r=mid-1,ans=mid;else l=mid+1; 19 } 20 printf("%d",ans); 21 return 0; 22 }

 

20160517

转载于:https://www.cnblogs.com/YuanZiming/p/5732632.html

总结

以上是生活随笔为你收集整理的bzoj4525[Usaco2016 Jan]Angry Cows的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。