POJ2456 Aggressive cows(二分+贪心)
二分 贪心 cows
2023-09-14 09:09:02 时间
如果C(d)为满足全部牛之间的距离都不小于d。
先对牛舍的位置排序,然后二分枚举d,寻找满足条件的d。
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<queue> #include<set> #include<map> #include<vector> #include<cmath> #define ll __int64 #define INF 0x3fffffff using namespace std; int n,m; int x[100005]; bool C(int d) { int num=1; int a=x[0]; int i=1; while(num<m) { if(a+d<=x[i]) { num++; a=x[i]; i++; } else i++; if(i==n) break; } if(num==m) return true; else return false; } void solve() { int l=0,r=x[n-1]+1; while(r-l>1) { int mid=(r+l)/2; if(C(mid)) l=mid; else r=mid; } cout<<l<<endl; } int main() { //freopen("d:\\Test.txt","r",stdin); cin>>n>>m; for(int i=0;i<n;i++) { scanf("%d",&x[i]); } sort(x,x+n); solve(); return 0; }
相关文章
- Java实现 LeetCode 785 判断二分图(分析题)
- 数据结构与算法之美-7 二分查找 跳表 [MD]
- 数的范围(整数二分)
- python 二分查找代码
- 826. 安排工作以达到最大收益-自定义快速排序+贪心算法+二分查找
- LCP 52. 二叉搜索树染色-先序遍历加二分查找
- 7-1 二分查找 (三种代码)
- VB编程:对数组进行二分查找-29_彭世瑜_新浪博客
- TOJ 3750: 二分查找
- 785. 判断二分图——本质上就是图的遍历 dfs或者bfs
- BST二叉树的二分查找
- 两个有序数组的中位数(第k大的数)——使用二分答案的思路写起来更直观
- 二分查找
- 【algorithm】算法基础课---二分查找算法(附笔记 | 建议收藏)