可乐饮料机

霍建华 发表于 2019-3-9 22:58
哈哈群主youxiu

偷偷hack你一下.

咦，你是群里的哪位呀？
你的例子很好。所以，youxiu的你应该想得到，从上往下的话，递归层数太多就会爆栈。所以我们可以从下往上，思路一毛一样，不过就是写成DP的形式啦。

**首次发代码，给一个naive的递归解法，指数级时间复杂度O(2^N)

struct interval

{

   int start;

   int end;

   interval(int a, int b)

   {

      start = a;

      end = b;

   }

};

bool getCoca(vector<interval> vec, interval target, int depth)

{

   if(depth == vec.size()) return false;

   if(target.start <= vec[depth].start && target.end >= vec[depth].end) return true;

   if(target.start > vec[depth].start && target.end > vec[depth].end)

   {

      if( getCoca(vec, interval(target.start-vec[depth].start, target.end-vec[depth].end), depth+1))

      {

         return true;

      }

   }

   return getCoca(vec, target, depth+1);

}

int main()

{

   vector<interval> vec;

   vec.push_back(interval(100,120));

   vec.push_back(interval(200,240));

   vec.push_back(interval(400,410));

   cout<<getCoca(vec, interval(300,360), 0)<<endl;

   return 0;

}

霍建华 发表于 2019-3-9 22:58
哈哈群主youxiu

偷偷hack你一下.

Get 到楼主的point， 不过你举得例子这种是不是一下就判断成功，就退出了？

霍建华 发表于 2019-3-10 04:52
为什么, 你怎么判断出来的? 假如现在变[1, 2]呢

失误，没注意到target.start >> vec[i].start