poj2566 B - Bound Found(尺取)
思路来源
https://www.jianshu.com/p/4604504a9810
题意
给n个数,取部分连续和的绝对值,使之与给定的t尽可能接近。
输出这部分和的绝对值,左下标和右下标。
心得
尺取需要排序维护单增的序列,
这样才能大了推左端界使之更小,小了推右端界使之更大。
前缀和也是可以排序的,由于是绝对值,所以不影响。
作差的时候取一下绝对值就可以,预存它们的位置。
下标从1到n还是有点好处,可以统一前缀和p[r].sum-p[l].sum操作。
输入时输入p[1]-p[n],前缀和维护,
这里我们插入一个sum=0,pos=0的点p[0]参与排序。
这样再后续处理时,l遇到这个点,
代表取前p[r].pos个数进行求和,此处用减0,这就统一了操作。
l==r是没有意义的,一定要两个不同的下标减否则没有选中元素。
注意前缀和作差,
[1,rpos]减[1,lpos]为(lpos,rpos],
故答案为[lpos+1,rpos]。
下标问题Debug很久啊真的很迷……
代码
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const int INF=0x3f3f3f3f;
const int MAXN=1e5+10;
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int>
#define si set<int>
#define pii pair<int,int>
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
ll n,num,a[MAXN],k,l,r,lpos,rpos,ans,delta,mindelta;
struct node
{
ll sum;
ll pos;
}p[MAXN];
bool operator<(node a,node b)
{
if(a.sum!=b.sum)return a.sum<b.sum;
else return a.pos<b.pos;
}
void init()
{
l=0;r=1;
mindelta=INF;
}
int main()
{
while(~scanf("%lld%lld",&n,&num)&&(n+num))
{
rep(i,1,n)
{
scll(a[i]);
if(i==1)p[i].sum=a[i];
else p[i].sum=p[i-1].sum+a[i];
p[i].pos=i;
}
p[0].sum=0,p[0].pos=0;
sort(p,p+n+1);//单增前缀和 才能尺取 保留下标故无影响 期间一个0也要考虑在内
rep(i,1,num)
{
init();
scll(k);
while(r<=n&&mindelta)//为0肯定最符合要求,首先保证p[0].sum是无意义的0,1-n的下标优势
{
delta=p[r].sum-p[l].sum;if(delta<0)delta=-delta;
ll tmp=delta-k;if(tmp<0)tmp=-tmp;
if(tmp<mindelta)//如果更接近k
{
mindelta=tmp;
ans=delta;
lpos=p[l].pos;
rpos=p[r].pos;
}
if(delta>k)l++;
if(delta<k)r++;
if(l==r)r++;//确保两个不同的下标作差
}
if(lpos>rpos)swap(lpos,rpos);
printf("%lld %lld %lld\n",ans,lpos+1,rpos);//前缀和作差[1,rpos]-[1,lpos]为(lpos,rpos],故为[lpos+1,rpos]
}
}
return 0;
}