题意:
找出区间和为m的所有段,并输出。
如果找不到,就找到比m大且与m差值最小的段。
思路:
尺取法
ac代码:
//尺取法
#include<bits/stdc++.h>
using namespace std;
int a[110000];
struct nod{int l,r;nod(){}nod(int ll,int rr){l=ll;r=rr;}
};
int main(){int n,m;cin>>n>>m;for(int i=0;i<n;i++) cin>>a[i];int mx=9999,fl=0;int l=0,r=0,sum=0;queue<nod> que;while(1){while(r<n&&sum<m)sum+=a[r++];if(sum<m) break;if(sum==m){fl=1;printf("%d-%d\n",l+1,r);} if(sum-m<mx){mx=sum-m;while(que.size())que.pop();que.push(nod(l+1,r));} else if(sum-m==mx){que.push(nod(l+1,r));} sum-=a[l++]; }if(fl!=1){while(que.size()){nod x=que.front();printf("%d-%d\n",x.l,x.r);que.pop();}}return 0;
}