題意：
? ? ? 給你一個正整數(shù)序列，問你在里面找到一個最短的子序列，要求子序列的和大于等于k，輸出序列長度。


思路：
? ? ? 這個序列的每個數(shù)字都是正整數(shù)，那么就比較好想了，我們可以直接枚舉終點，然后每次當當前和大于等于k的時候就把前面的markid(markid初始為1)點縮進，得到前端（我的是得到前端的下一個，這個無所謂，就是一個加不加1的事），然后更新最小值就行了，這樣的時間復雜度是O(n)的，還有一個O(n*logn)的方法，就是白書上說的那個，我們可以枚舉終點，然后二分去找起點，因為所有數(shù)字都是正整數(shù)，所以是單調(diào)的，找到最靠后的起點作為當前終點的起點，然后更新最小值就行了。


#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;
}

總結(jié)

以上是生活随笔為你收集整理的LA2678最短子序列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。