POJ2566 尺取法巧解

本文主要是介绍POJ2566 尺取法巧解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define N 100050
#define INF 2000000010//数要开大一点避免溢出
int a[N],ans,n,t,k;
struct Node
{int v,id;
}sum[N];
bool cmp(Node a,Node b)
{return a.v<b.v;
}void solve(int a[])
{ans=INF;int l=0,r=1;int anss,ansl,ansr;while(l<=n&&r<=n){int w=abs(sum[r].v-sum[l].v);//前n个数的和相减，结果一定是连续的。int q=abs(w-t);if(q<ans){anss=w;ans=q;ansl=sum[l].id;//ansl为实际a数组的边界，l,r为sum数组的左右端点ansr=sum[r].id;}if(w>t) l++;else if(w<t) r++;else break;if(l==r) r++;}if(ansl>ansr) swap(ansl,ansr);printf("%d %d %d\n",anss,ansl+1,ansr);
}int main()
{while(~scanf("%d %d",&n,&k)&&(n+k)){sum[0].v=0;sum[0].id=0;for(int i=1;i<=n;i++){scanf("%d",&a[i]);sum[i].v=sum[i-1].v+a[i];sum[i].id=i;}sort(sum,sum+1+n,cmp);while(k--){scanf("%d",&t);solve(a);}}return 0;
}
//尺取法必须在单调数组中才能使用，所以要把a数组前i个数的和求出来进行排序。注意要有sum[0]=0，因为要计算单独一段的绝对值的和

这篇关于POJ2566 尺取法巧解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---