题解 SP297 【AGGRCOW - Aggressive cows】

- 虽然是道水题，但是题解也不能太随便了$qwq$ - 在我的[Blog](https://www.17shou.vip/2019/04/21/SP297-AGGRCOW-Aggressive-cows/)查看，可以获得更好的阅读体验。 - 这是一道3倍经验题： - [P1824 进击的奶牛](https://www.luogu.org/problemnew/show/P1824) - [P1316 丢瓶盖](https://www.luogu.org/problemnew/show/P1316) - [SP297 AGGRCOW - Aggressive cows](https://www.luogu.org/problemnew/show/SP297) ------ - 可以想象出有一个轴，最暴力的算法我们可以想到：从小到大枚举最小距离的值$（dis）$，然后检验，如果发现有一次不行了，那么上次枚举的就是最大值。检验的方法使用贪心，先把$C$数组进行一次排序，枚举每一个点$i$是否比上一个点$last$的距离$\geq dis$，如果是，就在这里放一只牛，更新$last$；如果否，就比对下一个点。如此反复。如果无法在实现在当前最小距离下，放$c$条牛，那么这个$dis$就不可取。 - 先在回头再看，可以发现从小到大枚举$dis$值具有单调性，所以可以考虑用二分查找这个$dis$。 - 最坏复杂度$O(T \times nlogn)$ - $Code$：还有不懂的看代码$\Downarrow \Downarrow$ ```cpp #include <iostream> #include <cstdio> #include <algorithm> #define INF 999999999 using namespace std; int C[100005],n,c,T; int l,r; inline void solve(){ scanf("%d%d",&n,&c); for (int i=1;i<=n;i++){ scanf("%d",&C[i]); } sort(C+1,C+n+1);//贪心是要排序的 int l=1,r=1e9,Mid;//r直接10^9，反正是log，没有什么区别。 while (l<r){ int last=-INF; int flag=0;//已经放的牛的数量 Mid=(l+r+1)>>1;//记得要+1，否则死循环！ for (int i=1;i<=n;i++){ if (C[i]-last>=Mid){//这个就是贪心检验 flag++; last=C[i]; } if (flag>=c) break;//如果可以满足直接退出，再往后面扫也一定满足 } if (flag>=c) l=Mid; else r=Mid-1; } printf("%d\n",l); return; } int main(){ scanf("%d",&T);//题目中是有数据组数的 while (T--) solve(); return 0; } ``` - ~~如果觉得不错，可以给我点赞啊$qwq$~~