#include<iostream>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<set>
#include<cstring>
#include<stdio.h>
#include<queue>
using namespace std;
typedef pair<int,int> P;
const int MAXN = 1e5+99;
int sum[MAXN], val[MAXN];
vector<P> vec;
int N, M, MIN=1e9;
int main() {
int num;
scanf("%d%d",&N, &M);
for(int i = 1; i <= N; i++) {
scanf("%d",&num);
val[i] = num;
sum[i] = sum[i-1]+num;
}
int l = 1, r = 1;
while(r <= N) {
int temp = sum[r] - sum[l] + val[l];
if(temp >= M) {
if(MIN < temp-M) {
//l++;
//continue;
}
else if(MIN > temp-M){
MIN = temp-M;
vec.clear();
vec.push_back(P(l,r));
}else {
vec.push_back(P(l,r));
}
l++;
if(l > r) {
r++;
}
}else {
r++;
}
}
for(int i = 0; i < vec.size(); i++) {
P p = vec[i];
cout << p.first << "-" << p.second << endl;
}
}
直接用双端点枚举会超时，这里采用尺取法。 答案的存取 起初我想的是就直接开一个10^8的数组，按照差值存在对应的数组，但是会超内存。因此又想到了 算法笔记中用单个数组保存的方法。
转载于:https://www.cnblogs.com/dcklm/p/10350402.html
