[POJ 3061][雙指針] Subsequence

原題連結
這題也是相當經典的單調性的題目
提供兩個我想過的解法：

1.
建出前綴和pre，那麼題目相當於問說最小的k使得pre[R]-pre[R-k]>=M
首先，因為序列裡都是正整數，pre具有單調性，可以二分搜求解，時間O(nlgn)

(如果序列並非皆為正整數呢？那就使用deque維護單調性，仍然可以二分搜)

2.
就是code中的解法。
維護兩個指針L,R，我們對於每個L都快速的找到最小的滿足條件的R。
觀念非常類似滑動視窗。最核心的概念是：

如果滿足L0的最小R叫做R0，那麼滿足L0+1的最小R一定>=R0

注意，這個性質在序列並非皆為正整數時將失效。(想一想，為什麼)

那麼，我們就可以讓L遞增的同時讓R遞增到他該在的位置，然後更新答案。
因為L和R都最多遞增n次，時間複雜度O(n)。

#include<cassert>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
const int maxn=100000+5;
const int INF=(1<<30);
int a[maxn];
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        for(int i=0;i<n;i++) scanf("%d",a+i);
        
        int sum=0,ans=INF;
        for(int L=0,R=-1;;sum-=a[L++])
        {
            while(sum<m && R+1<n) R++,sum+=a[R];
            if(sum<m) break;
            ans=min(ans,R-L+1);
        }
        printf("%d\n",ans==INF?0:ans);
    }
}