題意： 給你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為真，說明此時這個距離滿足條件，繼續(xù)尋找更滿足條件的距離}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; }

總結(jié)

以上是生活随笔為你收集整理的nyoj--586（疯牛） poj --2456的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。