红魔馆爆炸了---湖南科技大学oj1975---尺取法

                                        **红魔馆爆炸了**

题目描述
红魔馆最近迎来了两块陨石，由于防范不到位，第一块陨石从天而降，红魔馆爆炸了。馆主蕾米莉亚有着强大的力量，她决定阻止第二块陨石，方法是将陨石打爆，使其分裂成若干个小石块。为了简化问题，我们可以将一块陨石看作由连续的n个石块组成，每个石块包含了一定能量，蕾米莉亚需要毁掉其中某一段连续的石块(该段能量和为s)，被毁掉的石块将会消失，且因连锁反应还会使剩余石块总能量减少s，蕾米莉亚需要保证剩余石块总能量不大于m，红魔馆就能保存下来。蕾米莉亚想知道她最短需要毁掉的连续石块长度。

输入：
有多组输入，每组输入第1行为两个数字n、m(1<=n<=100000，1<=m<=10^9)，表示总共有n个石块，蕾米莉亚需要将剩余总能量控制在不大于m。接着n行，每行包含一个整数ai，表示第i个石块的能量(1<=ai<=10000)。 各组数据的n总和不超过1000000。

输出
每组输出一行，只包含一个整数，表示最少需要毁掉的连续石块长度。

样例输入
5 5
1 2 3 4 5
5 4
1 2 3 4 5

样例输出
1
2

来源：
汤越凡，2019年湖南科技大学校赛

题源链接

题意： 找到一个序列，使总能量减去该序列能量和的两倍后能量小于或等于m,求最小的该序列长度；

**解题思路：**用尺取法求最短长度；

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <queue>
 
using namespace std;
 
int main()
{
    long long n, m, a[100000];
    while(scanf("%lld %lld",&n,&m)!=EOF)        //多组输入
    {
        long long sum=0;
        for(int i=0;i<n;i++)
        {
            scanf("%lld",&a[i]);
            sum=sum+a[i];
        }
        long long k=0, l=0, r=0, mi=n+1;
        while(1)
        {
            if(m>=sum)       //如果m大于总能量sum则直接退出循环。
                break;
            for(;sum-2*k>m&&r<n;r++)
            {
                k=k+a[r];
            }
            if(sum-2*k>m)
                break;
            else
            {
                mi=min(mi,r-l);
            }
            k=k-a[l++];
        }
        if(mi>n)
            mi=0;
        printf("%lld\n",mi);
    }
    return 0;
}

谢谢，第一次写，见谅。