这道题确实有点超出我的能力范围,参考了别人的博客,下面这个版本是我能懂也是大致想到但是无法实现的代码。
注意:
起止范围是从1开始的
当然也有用二分法解的,等我刷第二遍的时候再来补吧。
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,m,p,q=1,ans=0,M=0x7fffffff;
cin>>n>>m;
vector<int> dim(n+1),res;
dim[0]=0;
for(int i=1;i<=n;i++){ //注意是从1开始
cin>>dim[i];
}
for(p=0;p<=n;p++){
ans -= dim[p]; //类似于滑动窗口
while(q<=n && ans < m){
ans += dim[q++];
}
if(ans >= m && ans < M){
M = ans;
res.clear();
res.push_back(p+1);
res.push_back(q-1);
}else if(ans == M){
res.push_back(p+1);
res.push_back(q-1);
}
}
for(int i=0;i<res.size();i+=2){
cout<<res[i]<<"-"<<res[i+1]<<endl;
}
return 0;
}