首页 > 代码库 > POJ - 2566 Bound Found（尺取法+前缀和）
POJ - 2566 Bound Found（尺取法+前缀和）
题目链接：http://poj.org/problem?id=2566
题意：给定一个序列（n个整数）和一个整数k（m个），求出这个序列的一个子串，使之和的绝对值与k的差最小。
尺取法的题目有两个特性：
1. 所求的序列是一个连续的序列，这样才能将序列抽象成一个头和一个尾来描述。
2. 头尾枚举的序列满足某种单调的性质，这样才能进行尺取的操作。
这个序列是一个随意的序列，不可能直接对其进行操作，先要预处理下，进行前缀和操作，把对应的值和标记放在同一个pair。
然后根据前缀和的值进行排序，这样就符合尺取法的两个特性了。
其他的就是一些细节上的东西了。直接上代码，(•‾??‾?•)??°，
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 5 const int INF=0x3f3f3f3f; 6 const int N=100011; 7 pair <int,int> T[N]; 8 9 //前缀和初始化10 void init(int n){11 T[0]=make_pair(0,0);//这里需要放一个0,0进去,不然有一些值就取不到了. 12 int x,tmp=0;13 for(int i=1;i<=n;i++){14 scanf("%d",&x);15 tmp+=x;16 T[i]=make_pair(tmp,i);17 }18 sort(T,T+n+1);19 }20 21 int main(){22 int n,m;23 while(scanf("%d %d",&n,&m)){24 if(n==0&&m==0) break;25 init(n);26 for(int i=1;i<=m;i++){27 int l=0,r=1,t=INF;28 int tmp,ansl,ansr,ans;29 scanf("%d",&tmp);30 while(r<=n&&t){31 int temp=T[r].first-T[l].first;32 if(abs(temp-tmp)<t){33 t=abs(temp-tmp);34 ans=temp;35 ansl=T[l].second;36 ansr=T[r].second;37 }38 if(temp<tmp) r++;39 if(temp>tmp) l++;40 if(temp==tmp) break;41 if(l==r) r++; //保证r>=l 42 }43 if(ansl>ansr) swap(ansl,ansr);//因为是经过排序过的,有可能左边的比右边的大. 44 printf("%d %d %d\n",ans,ansl+1,ansr);//左边多加了一个0,需要+1 45 }46 }47 return 0;48 }
POJ - 2566 Bound Found（尺取法+前缀和）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。