首页 > 代码库 > hdu 4932 /bestcoder B题 #4 /思维题

hdu 4932 /bestcoder B题 #4 /思维题

题意:给一个数列(整数),用一些不相交的区间去覆盖(只能是用端点去覆盖,端点可以交)。而且区间出度相等。求最大区间长度。

开始一下就敲了,枚举每个区间长度,判断合法,更新最大。但是后来一看小数,感觉不行,改为二分,后来还是挂了。。。

赛后才知道,二分的时候,答案必需要满足单调性啊,这里小的数据不行,大的数据可以行!如 0 1 5 6 10, 3不行,4行。

后来才知道,枚举时,每个差值的一半也是可以的:仔细想想很容易证明。(水,坑)

#include<iostream>
#include<vector>
#include<cstdio>
#include<algorithm>
using namespace std;
vector<int>v; int n;
bool ok(double tmax)
{
    int fl=-1;
    for(int j=1;j<n-1;j++)
    {
        if(fl==-1)          //之前的放在前
        {
          if(v[j]-tmax<v[j-1])  //放前面不行,放后面:
            {
             if(v[j]+tmax<=v[j+1])  //放后面
                {
                   fl=1;
                   if(v[j]+tmax==v[j+1])    //下一个免了
                    {
                        j++;
                        fl=-1;
                    }
                 }
             else         //否则不行
                 return 0;
            }
            else    //放前面
                 fl=-1;
        }
         else          //之前的在后面,
            {
                if(v[j]-tmax<v[j-1]+tmax) //放前面放不来
                  {
                     if(v[j]+tmax<=v[j+1])
                       {
                          fl=1;
                         if(v[j]+tmax==v[j+1])
                             {
                                 j++;
                                 fl=-1;
                             }
                        }
                     else
                     {
                         return 0;
                     }
                  }
                  else
                  {
                      fl=-1;
                  }
            }
    }

    return 1;
}
vector<double>dis;
int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        int tx=0;
        v.clear();
        dis.clear();
        for(int i=0;i<n;i++)
          {
              cin>>tx;
            v.push_back(tx);
          }
         sort(v.begin(),v.end());
          for(int i=0;i<n-1;i++)
          {
             double d=v[i+1]-v[i];
             dis.push_back(d);
             dis.push_back(d/2.0);
          }
       sort(dis.begin(),dis.end());
       for(int i=dis.size()-1;i>=0;i--)
        {
           if(ok(dis[i]))
           {
             printf("%.3lf\n",dis[i]);
             break;
           }
       }

    }
    return 0;
}