AcWing 1528. 火星购物
原题链接
中等
作者:
leo123456
,
2020-08-30 12:29:26
,
所有人可见
,
阅读 1151
#include<iostream>
#include<cstring>
using namespace std;
const int N=100010,INF=1e9;
int n,m;
int s[N]; //前缀和
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&s[i]);
s[i]+=s[i-1];
}
int res=INF;
for(int i=1,j=0;i<=n;i++) //j,i,双指针
{
while(s[i]-s[j+1]>=m) j++;
if(s[i]-s[j]>=m) res=min(res,s[i]-s[j]);
}
for(int i=1,j=0;i<=n;i++)
{
while(s[i]-s[j+1]>=m) j++;
if(s[i]-s[j]==res) printf("%d-%d\n",j+1,i);
}
return 0;
}
大佬问一下为啥从j+1开始比较
由于我们所看的序列是从j+1到i,若s[i]-s[j+1]>=m的意思是当j+1这个钻石有些多余,去掉它也可以凑出m,由于我们需要求最小值,所以就将它舍弃,即j++。