Bound Found [POJ2566] [尺取法]-白红宇

Bound Found [POJ2566] [尺取法]

阅读量：5254 次

发布时间：2019-06-14

本文共 1992 字，大约阅读时间需要 6 分钟。

题意

给出一个整数列，求一段子序列之和最接近所给出的t。输出该段子序列之和及左右端点。

Input

The input file contains several test cases. Each test case starts with two numbers n and k. Input is terminated by n=k=0. Otherwise, 1<=n<=100000 and there follow n integers with absolute values <=10000 which constitute the sequence. Then follow k queries for this sequence. Each query is a target t with 0<=t<=1000000000.

Output

For each query output 3 numbers on a line: some closest absolute sum and the lower and upper indices of some range where this absolute sum is achieved. Possible indices start with 1 and go up to n.

Sample Input

5 1-10 -5 0 5 10310 2-9 8 -7 6 -5 4 -3 2 -1 05 1115 2-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -115 1000 0

Sample Output

5 4 45 2 89 1 115 1 1515 1 15

分析

这道题可以看得出来是要用尺取法，尺取法的关键是要找到单调性。而序列时正时负，显然是不满足单调性的。

如果记录下前缀和，并排好序，这样就满足单调性了，就可以使用前缀和了

代码

1 #include
      
        2 #include
        3 #include
        
          4 #include
         
           5 #include
          
            6 #include
           
             7 #include
            
              8 #include
             
               9 #include
              
               10 #define RG register int11 #define rep(i,a,b) for(RG i=a;i<=b;++i)12 #define per(i,a,b) for(RG i=a;i>=b;--i)13 #define ll long long14 #define inf (1<<30)15 #define maxn 10000516 using namespace std;17 int n,k;18 int num[maxn];19 struct P{20 int id,s;21 inline int operator < (const P &a)const{22 return s==a.s?id
               
                
                 '9'){ if(c=='-')f=-1;c=getchar();}29 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}30 return x*f;31 }32 33 void solve()34 {35 int aim=read();36 int l=0,r=1,mn=inf,al,ar,ans;37 while(l<=n&&r<=n&&mn)38 {39 int cal=p[r].s-p[l].s;40 if(abs(cal-aim)
                 
                  aim) ++l;46 else if(cal
                  
                   ar) swap(al,ar);51 printf("%d %d %d\n",ans,al+1,ar);52 }53 54 int main()55 {56 while(1)57 {58 n=read(),k=read();59 if(!n&&!k) return 0;60 rep(i,1,n) num[i]=read();61 p[0]=(P){ 0,0};62 rep(i,1,n) p[i].s=p[i-1].s+num[i],p[i].id=i;63 sort(p,p+1+n);64 rep(i,1,k) solve();65 }66 return 0;67 }

View Code

转载于:https://www.cnblogs.com/ibilllee/p/9300321.html

你可能感兴趣的文章