初识滑块思想

今天在做洛谷题目P5745 【深基附B例】数列求和的时候发现一种新的思想——滑块思想。在这里分享给大家。

我们根据这道题目的大意来说吧：其实就是让你找到一段连续的数列，使得它们的和不超过m且最大。让找出这个序列。

一开始的我只能想到$O(n^2)$的暴力加前缀和的优化。但是发现这个数值范围（$4\ast 10^6$）有点大，做不出来。（突然大囧），于是我上题解寻求帮助，发现了一种新的思考方式——滑块思想。

用说来其实非常简单，实现方法有点类似于双指针的操作方式。

一开始，两个指针都指向最左侧的元素，然后右指针不断右移。如果中间的和小于等于m的话，那有指针就可以不停的移动下去，如果大于m，就把左指针右移，然后和曾经的最大结果结果取较大值。等左右指针都归到最右侧的时候。就可以得出它们的最大值是多少了。

一开始我有点奇怪，不知道为什么这样做是对的，后来我明白了为什么他是正确的。

我们再看看题目，他有3个要求： 1.数列必须连续 2.和不许超过m 3.要求和最大

在我们刚才的处理过程中，左指针和右指针刚好能够围成一个连续的区间——条件1满足了。

在右指针右移的过程中，如果和大于m左指针就会右移，也可以保证它们的和是小于等于m的——条件2满足了

我们每一次都在区间中取最大值，又遍历了整个不大于m的区间——条件3满足了

三个条件都可满足，综上：这样做是正确的

最后，在这里附上本题的AC代码：

我的AC评测记录

#include <bits/stdc++.h> using namespace std; long long n,m; long long a[4000000]; long long total,maxn = -(0x3f3f3f3f); long long ans_l,ans_r; inline void change(long long x,long long l,long long r){//交换函数 if(x>maxn){ maxn = x; ans_l = l; ans_r = r; } return; } int main(){ scanf("%lld %lld",&n,&m); for(long long i=0;i<n;++i){ scanf("%lld",&a[i]); } //重头戏开始了： long long l,r;//定义双指针 l=0,r=0;//最开始把两个指针都放在最左侧 total = a[0];//total最开始只框柱[0,0] while(r < n){//疯狂循环 while(1){ if(r<n){//不到边界 ++r;//指针右移 total += a[r];//增加这个新元素 if(total > m){//如果新加入的这个值有问题，需要左指针释放部分值，就直接跳出 break; } change(total,l,r);//能执行到这里说明当前的total是符合题意的，可以比较 } else{ break;//到达边界不能再移动了 } } while(1){ if(l<=r){//左指针在右指针的左侧 total -= a[l++];//缩写，指针右移，释放元素 if(total <= m){//这个值是否合法？ //合法就比较 change(total,l,r); break; } } else{ break;//休想越过右指针 } } } printf("%lld %lld %lld",ans_l+1,ans_r+1,maxn);//输出结果就好了 return 0; }

希望这种思想能帮助到您，感谢您的耐心观看。