题目:http://pat.zju.edu.cn/contests/pat-a-practise/1044
题解:
在一个长度为n的序列中找长度为m的连续子序列,如果不存在,则找大于m的最小连续子序列长度。
最后输出所有符合条件的连续子序列的两个端点。
枚举加二分搜索。
代码:
#include<cstdio> #include<cstring> #include<cmath> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<algorithm> using namespace std; #define INF 0x6fffffff int summ[100005]; struct point { int st,en; }node; vector<struct point> out; int binarySearch(int l,int r,int m,int &j)//二分查找 { int i=l; int mid; for(;l<r;) { mid=(l+r)/2; if(summ[mid]-summ[i-1]>=m) r=mid; else l=mid+1; } j=r; return summ[j]-summ[i-1]; } int main() { int n,m; scanf("%d%d",&n,&m); summ[0]=0; for(int i=1;i<=n;++i) { scanf("%d",summ+i); summ[i]+=summ[i-1];//记录累加和 } int best=-1; for(int i=1,j,temp;i<=n;++i) { temp=binarySearch(i,n,m,j); if(best==-1||(m<=temp&&temp<best))//如果值大于等于m且小于之前的最佳值 { best=temp; out.clear();//清空记录 node.st=i; node.en=j; out.push_back(node); } else if(best!=-1&&temp==best)//如果值等于之前的最佳值 { node.st=i; node.en=j; out.push_back(node);//添加新段 } } int len=out.size(); for(int i=0;i<len;++i) printf("%d-%d\n",out[i].st,out[i].en); return 0; }