AcWing 1528. 火星购物
原题链接
中等
作者:
RainSure
,
2022-02-24 21:32:07
,
所有人可见
,
阅读 193
前缀和加双指针
#include<iostream>
#include<cstring>
using namespace std;
const int maxn = 100010, inf = 1e9;
int s[maxn];
int n, m;
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i ++){
cin >> s[i];
s[i] += s[i - 1];
}
int res = inf;
for(int i = 1, j = 0; i <= n; 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) cout << j + 1 << "-" << i << endl;
}
return 0;
}
请问前缀是指什么算法啊
前缀和