Day3-尺取，差分，前缀和
前缀和！！！这个是我开营以来遇到过的最简单的知识点。非常好用！！！
思想主要就是统计从起点到第i个点的数值总量。
直~接~上~代~码~
#include <bits/stdc++.h>
using namespace std;
long long sum[100010];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
sum[i]=sum[i-1]+x;
}
for(int i=1;n;i++)
{
cout<<sum[i]<<” “;
}
return 0;
}
差分，主要用于解决某个区间序列的加和问题，其思想就是前缀和的逆运算。
代码如下:
#include <bits/stdc++.h>
using namespace std;
int cf[500010];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>cf[i];
}
for(int i=1;i<=n;i++)
{
cf[i]=cf[i-1]+cf[i];
cout<<cf[i]<<" ";
}
return 0;
}
双指针（或叫尺取法），是一种优化算法，就是搞两个变量代替二重循环，但其实一个变量变了，另一个也会发生变化，所以时间复杂度就是O(n);
这个最好用一道提来讲:
Problem ID: 8091
时间：1s 空间：256M
题目描述：
给定一个含有 n 个整数的数组和一个整数 s ，找出该数组中满足其和 ≥s 的长度最小的连续子数组。
如果不存在符合条件的连续子数组，输出 0。
输入格式：
第一行包含一个整数 T，表示测试数据组数。
对于每组测试数据，
第一行包含两个整数 n, s。
接下来包含 n 个整数 ai
输出格式：
对于每组测试数据，输出一个整数表示答案。
样例1
3
8 7
2 3 1 2 0 4 3 0
8 100
2 3 1 2 0 4 3 0
3 0
1 1 1
样例输出
2
0
1
#include <bits/stdc++.h>
using namespace std;
int main()
{
int q;
cin>>q;
while(q--)
{
int f[300010];
int minn=1e9;
long long sum=0;
long long n,s;
cin>>n>>s;
for(int i=1;i<=n;i++)
{
cin>>f[i];
}
for(int i=1,j=0;i<=n;i++)//双指针i,j
{
while(sum<s && j<=n)//如果总数没有到s就一直向右找
{
j++;
sum+=f[j];
}
if(sum>=s)//如果成立
{
minn=min(j-i+1,minn);//比较谁小
}
sum-=f[i];
}
if(s==0) cout<<"1"<<endl;//特判
else cout<<(minn==1e9?0:minn)<<endl;//三目运算符应该都懂吧
}
return 0;
}