nyoj--586（疯牛） poj --2456

题意： 给你n个点，在这n个点中插入m个点，使得m个点的距离尽可能的大，求尽可能大的距离值最小

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,m,a[100005]; bool Greedy(int cur)//贪心查找符合条件的距离 {int ret = a[0];int count = 0;for(int i = 1;i < n;i++){if(a[i] - ret >= cur){count ++;ret = a[i];}}if(count >= m-1) return true;//当满足大于、等于 m - 1，说明存在，返回true；return false; } void search(int l,int r)//二分枚举这个距离 {while(l <= r){int mid = (l + r) / 2;if(!Greedy(mid)) r = mid - 1; //if为假，说明此时这个距离太大，不符合条件else l = mid + 1; //if为真，说明此时这个距离满足条件，继续寻找更满足条件的距离}printf("%d\n",l-1); } int main() {while(scanf("%d%d",&n,&m)!=EOF){for(int i = 0;i < n;i++)scanf("%d",&a[i]);sort(a,a+n);search(0,a[n-1]);}return 0; }

总结

以上是生活随笔为你收集整理的nyoj--586（疯牛） poj --2456的全部内容，希望文章能够帮你解决所遇到的问题。

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