首页 > 代码库 > POJ 2566：Bound Found（Two pointers）
POJ 2566：Bound Found（Two pointers）
【题目链接】 http://poj.org/problem?id=2566
【题目大意】
给出一个序列，求一个子段和，使得其绝对值最接近给出值，
输出这个区间的左右端点和区间和。
【题解】
因为原序列的前缀和不具有单调性，难以处理，
因此我们对前缀和进行排序，同时保留前缀和的右端点做标识作用，
题目要求区段和的绝对值最接近目标，因此排序不会造成前后顺序变化造成的影响
现在题目转化为在一个有序数列中，求一个数对，使得差值最接近给出数，
利用单调性，可以尺取解决问题。
【代码】
#include <cstdio>#include <utility>#include <algorithm>#include <climits>using namespace std;const int N=100010,INF=INT_MAX;typedef pair<int,int> P;int n,m,s,t,ans,ansl,ansr;P p[N];int main(){ while(scanf("%d%d",&n,&m),n&&m){ p[0]=P(s=0,0); for(int i=1;i<=n;i++)scanf("%d",&t),p[i]=P((s+=t),i); sort(p,p+n+1); while(m--){ scanf("%d",&t); int l=0,r=1,Min=INF; while(l<=n&&r<=n){ int tmp=p[r].first-p[l].first; if(abs(tmp-t)<Min){ Min=abs(tmp-t); ans=tmp; ansl=p[l].second; ansr=p[r].second; }if(tmp>t)l++;else if(tmp<t)r++;else break; if(l==r)r++; }if(ansl>ansr)swap(ansl,ansr); printf("%d %d %d\n",ans,ansl+1,ansr); } }return 0;}POJ 2566：Bound Found（Two pointers）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。