首页 > 代码库 > poj2566 尺取法
poj2566 尺取法
题意：
输入 n m 之后输入n个数
之后m个询问 对于每个询问 输入一个t 输出 三个数 ans l r 表示从l 到 r的所有数的和的绝对值最接近t 且输出这个和ans
思路：就是指针的移动。
AC代码：
#include<iostream>#include<cstdio>#include<algorithm>#include<cmath>#include<cstring>#include<limits.h>using namespace std;pair<int,int>p[100005];int n,m,t,num;void find(int x){ int i=0,j=1,ans=INT_MAX,temp,l,r,v; while(j<=n && ans) { temp=p[j].first-p[i].first; if(abs(temp-x)<=ans) { ans=abs(temp-x); v=temp; l=p[i].second; r=p[j].second; } if(temp<x) j++; if(temp>x) i++; if(i==j) j++; } if(l>r) { int a=r; r=l; l=a; } printf("%d %d %d\n",v,l+1,r);}int main(){ while(scanf("%d%d",&n,&m)==2 && (m+n)) { int sum=0; p[0]=make_pair(0,0); for(int i=1; i<=n; i++) { scanf("%d",&num); sum+=num; p[i]=make_pair(sum,i); } sort(p,p+n+1); while(m--) { scanf("%d",&t); find(t); } } return 0;}
poj2566 尺取法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。