題意：
? ? ?給了一些處在x軸上的點，要求我們用長度相等的線段覆蓋所有點，線段和線段之間不能重疊，問線段最長可以使多長。

思路：

? ? ? 一開始一直在想二分，哎！感覺這個題目很容易就往二分上去想，但是其實仔細想想并不是滿足單調性的（對于我的方法是不滿足單調性的，別的方法有可能可以），一開始想的是不能出現連續的兩個不滿足，這里的滿足就是可以有線段，各種wa，說下正確的思路吧，這個是中午才想出來的，這個題目我們可以貪心，首先要明白，最后的答案只有兩種情況，要么是某兩個相鄰點的距離，要么是某個相鄰點距離的一半，所以我們把所有可能都枚舉一半，判斷是否滿足的時候可以用貪心的想法，對于每一個點，要么被左邊線段覆蓋，要么被右邊線段覆蓋，我們從左往右跑的話，那么就先判斷能不能被左邊覆蓋，不能的話在判斷能不能被右邊覆蓋，如果都不能那么當前長度就失敗了，至于判斷的細節很簡單，自己想下，想不出來看下下面的代碼就知道了。

#include<stdio.h> #include<algorithm>#define N 51 using namespace std;double dis[N] ,num[N]; int mk[N];int ok(double now ,int n) {mk[1] = 1;for(int i = 2 ;i < n ;i ++){double disl = dis[i-1] ,disr = dis[i];if(mk[i-1] == 1 && now <= disl || mk[i-1] == 2 && (now == disl || now <= disl / 2))mk[i] = 1;else if(now <= disr) mk[i] = 2;else return 0;}return 1; }double maxx(double x ,double y) {return x > y ? x : y; }int main () {int n ,i ,t;scanf("%d" ,&t);while(t--){scanf("%d" ,&n);for(i = 1 ;i <= n ;i ++)scanf("%lf" ,&num[i]);sort(num + 1 ,num + n + 1);for(i = 2 ;i <= n ;i ++)dis[i-1] = num[i] - num[i-1];double ans = 0;for(i = 1 ;i < n ;i ++){if(ok(dis[i] ,n))ans = maxx(ans ,dis[i]);else if(ok(dis[i]/2 ,n))ans = maxx(ans,dis[i]/2);}printf("%.3lf\n" ,ans);}return 0; }

總結

以上是生活随笔為你收集整理的hdu4932 小贪心的全部內容，希望文章能夠幫你解決所遇到的問題。

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