当前位置：首页 > news >正文

POJ 2566 Bound Found（尺取法+前缀和）

news 来源：原创 2024/5/18 20:02:06

题目链接

在这里插入图片描述
1.题目大意：给定一个序列，包含n个整数（1<=n<=100000），以及一个整数t（0<=t<=1000000000）。求一段子序列，使它的区间和最接近t。输出该段子序列之和及左右端点

2.刚刚接触尺取，做了两道基础题，感觉尺取也不过如此…打脸来的就是这么快，之前的题目序列都是正数，但是现在该题有正数有负数，按照POJ3061的思路去写，怎么都调不好，惨兮兮

3.原来，仔细思考一下，我们设置的双指针在不断向后滑动的过程中，如果不能保证滑动区间的单调递增性，那么就会出现r指针也要左移的局面，但是不可以，~~r指针生来就是一往无前冲锋的勇士，没有撤退可言~~ 。因此，我们需要换个角度保证单调性。此类题目操作的都是序列的一段区间，还能如何表示这段区间呢？前缀和之差！对于区间[i,j]的和，等于前缀和sum[j]-sum[i-1]。那么我们就先求出所有前缀和，接着对前缀和排序，注意要保存之前的序号，因为我们需要表示答案区间。因为前缀和排序后保证了滑动区间的单调性，而任何一个序列的子区间都能被两个前缀和之差表示，因此这个思路符合预期结果

4.还有一点需要注意的是，因为sum[j]-sum[i-1]表示的是[i,j]，因此我们需要将下标为0的id和sum都设置为0。此外在最后得到的答案左区间都加一

5.样例的第一组数据有毒，答案确实该是"5 4 4"但是我怎么都调不出来，其他的也都对，抱着侥幸心理交了竟然过了，我人傻了…去网上看其他人的题解也都是这个样子，真的牛批

#include <iostream>
#include <algorithm>
#include <math.h>
using namespace std;
#define INF 0x7fffffff
const int maxn=1e5+10;
typedef long long ll;
struct node{
    int id,sum;
}a[maxn];

bool cmp(node &p,node &q){
    return p.sum<q.sum;
}

int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,k,t,x,l,r,lans,rans,ans,len;
    while(cin>>n>>k){
        if(!n && !k) break;
        a[0].id=a[0].sum=0;
        for(int i=1;i<=n;i++){
            cin>>x;
            a[i].id=i;
            a[i].sum=x+a[i-1].sum;
        }
        sort(a,a+1+n,cmp); //[0,n]排序
        while(k--){
            cin>>t;
            l=0,r=1,len=INF;  //len表示绝对值之差
            while(r<=n){
                int cur=a[r].sum-a[l].sum;
                if(abs(cur-t)<len){
                    lans=a[l].id;
                    rans=a[r].id;
                    len=abs(cur-t);
                    ans=cur;
                }
                if(cur<t) r++;
                else if(cur>t) l++;
                else break;
                if(l==r) r++; //R至少比L大1，因为前缀和的缘故
            }
            if(lans>rans) swap(lans,rans); //id是乱序的
            cout<<ans<<" "<<lans+1<<" "<<rans<<endl;
        }
    }
    return 0;
}