hdu 4932 /bestcoder B題 #4 /思維題

hdu 4932 /bestcoder B題 #4 /思維題

題意：給一個數列（整數），用一些不相交的區間去覆蓋（只能是用端點去覆蓋，端點可以交）。而且區間出度相等。求最大區間長度。

開始一下就敲了，枚舉每個區間長度，判斷合法，更新最大。但是後來一看小數，感覺不行，改為二分，後來還是掛了。。。

賽後才知道，二分的時候，答案必需要滿足單調性啊，這裡小的數據不行，大的數據可以行！如 0 1 5 6 10， 3不行，4行。

後來才知道，枚舉時，每個差值的一半也是可以的：仔細想想很容易證明。（水，坑）

#include
#include
#include
#include
using namespace std;
vectorv; int n;
bool ok(double tmax)
{
    int fl=-1;
    for(int j=1;jdis;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int tx=0;
        v.clear();
        dis.clear();
        for(int i=0;i>tx;
            v.push_back(tx);
          }
         sort(v.begin(),v.end());
          for(int i=0;i=0;i--)
        {
           if(ok(dis[i]))
           {
             printf("%.3lf\n",dis[i]);
             break;
           }
       }

    }
    return 0;
}