點我啊~帶你去找它\(^o^)/~

一開始一點思路都沒有，壓根不知道它要求的是什么，然后問了一下班長，才明白題目的意思就是，給你N個點，要你找出最優解的C點，言簡意賅的即使說區間選點。

思路：

假設兩點最短的距離是d,那么兩個點之間的距離d'會有大于等于d的關系，從而從線性解轉化成固定解，從而用貪心的思想找到最小距離的最大值得d，值得注意的一點就是首先要選第一個邊界點，因為邊界的點一定符合其他的點的最短距離的最大化，但是其他的點就不一定，又用二分枚舉的方法來尋找的d的范圍。一開始d可是是兩盡頭的距離，你在d的范圍內找到了大于等于c個點時。雖然滿足題意但不是最優的解，換句話說就是用他們間最大距離二分直到最后他們之間的差值是相等的時候,才是最佳的。

#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; int n,c,a[100005]; int find( int x) {int i,cout=1,now=a[0];for(i=1;i<n;i++){if(a[i]-now>=x){ //printf("%d++\n",a[i]);now=a[i];cout++;}}if(cout>=c)return 1;elsereturn 0; } void twO() {int left=0,right=a[n-1]-a[0],wid;while(left<=right){ wid=(left+right)/2;if(find(wid))left=wid+1;elseright=wid-1;}printf("%d\n",left-1); }int main() {int i;while(scanf("%d%d",&n,&c)!=EOF){ memset(a,0,sizeof(a));for(i=0;i<n;i++)scanf("%d",&a[i]);sort(a,a+n);twO();}return 0; }

這里給出兩種二分的模版，用遞歸的思想

int find(int left,int right,int result) {int i,wid;if(left>right)return 0;wid=(left+right)/2;if(b[wid]==result)return 1;else if(b[wid]<result)return find(wid+1,right,result);else return find(left,wid-1,result); } 另一種 void twO() {int left=0,right=a[n-1]-a[0],wid;while(left<=right){ wid=(left+right)/2;if(find(wid))left=wid+1;elseright=wid-1;} }

總結

以上是生活随笔為你收集整理的二分枚举+贪心(nyist疯牛）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。