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最短子序列

最新文章

热门文章