LA2678最短子序列

题意：
      给你一个正整数序列，问你在里面找到一个最短的子序列，要求子序列的和大于等于k，输出序列长度。


思路：
      这个序列的每个数字都是正整数，那么就比较好想了，我们可以直接枚举终点，然后每次当当前和大于等于k的时候就把前面的markid(markid初始为1)点缩进，得到前端（我的是得到前端的下一个，这个无所谓，就是一个加不加1的事），然后更新最小值就行了，这样的时间复杂度是O(n)的，还有一个O(n*logn)的方法，就是白书上说的那个，我们可以枚举终点，然后二分去找起点，因为所有数字都是正整数，所以是单调的，找到最靠后的起点作为当前终点的起点，然后更新最小值就行了。


#include<stdio.h>


#define N 100000 + 10


int num[N];


int main ()
{
  int n ,m ,i ,Ans;
  while(~scanf("%d %d" ,&n ,&m))
  {
      for(i = 1 ;i <= n ;i ++)
      scanf("%d",&num[i]);
      int nows = 0 ,nowid;
      for(Ans = 0 ,nowid = 1 ,i = 1 ;i <= n ;i ++)
      {
         nows += num[i];
         if(nows >= m)
         {
            while(nows - num[nowid] >= m)
            {
                nows -= num[nowid];
                nowid ++;
            }
            if(!Ans || Ans > i - nowid + 1)
            Ans = i - nowid + 1;
         }
      }
      printf("%d\n" ,Ans);
   }
   return 0;
}

总结

以上是生活随笔为你收集整理的LA2678最短子序列的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。