NKOJ 3545 接近（DP+单调队列）

发表于 |
字数统计: 661字 | 阅读时长 ≈ 3min

P3545接近

问题描述

对于一个数字序列A，并且有若干询问。对于每个询问，要求求出一段在序列A中非空 的连续段使得这一段数字的总和的绝对值尽量接近P。

输入格式

第一行2个数N、T，表示序列的长度和询问的个数。
接下来一行N个整数，表示A序列。 接下来T行，每行一个数P表示询问。

输出格式

共输出T行，每行对应一个询问的答案。
输出3个数：第一个数为能够实现的最接近P 的数，后面两个数L、R表示A序列中的L到 R这一段数能实现这个答案。
如果存在多解，输出L最小的解；
如果还有多解，输出R最小的解。

样例输入

5 1
-10 -5 0 5 10
3

样例输出

5 2 2

数据范围

30%的数据 1<=N<=1,000。
60%的数据 1<=N<=10,000。
100%的数据 1<=N<=100,000，A 序列中数字绝对值<=10,000，T<=100，询问的 数字<=10^9

此题容易想到求出前缀和数组$Sum$，鉴于复杂度，需要一个$O(n)$的算法，但此时遇到的问题就是，前缀和数组并不具有单调性。
注意到题目中的绝对值，于是学习到了一个大胆的操作，将前缀和数组排序，强行维护单调性，而且位置坐标并不会对答案产生影响，于是就单调DP即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
struct node{ll v,c;};
bool cmp(node a,node b)
{
	if(a.v==b.v)return a.c>b.c;
	return a.v<b.v;
}
node S[123456];
ll n,T,x,L,ans,tmp,l,r;
void MD(int p,int q)
{
	int tx,ty,t;
	tx=S[p].c;ty=S[q].c;
	if(tx>ty)swap(tx,ty);
	t=S[p].v-S[q].v-x;
	if(t<0)t=-t;
	if(t<tmp)tmp=t,ans=S[p].v-S[q].v,l=tx,r=ty;
	if(t==tmp&&tx<l)l=tx,r=ty,ans=S[p].v-S[q].v;
	if(t==tmp&&tx==l&&ty<r)r=ty,ans=S[p].v-S[q].v;
}
void Work()
{
	L=0;tmp=1e18;
	for(int i=1;i<=n;i++)
	{
		while(L<i-1&&S[i].v-S[L+1].v>=x)L++;
		MD(i,L);if(L<i-1)MD(i,L+1);//更新答案
	}
	printf("%lld %lld %lld\n",ans,l+1,r);
}
int main()
{
	scanf("%lld%lld",&n,&T);
	for(int i=1;i<=n;i++)scanf("%lld",&x),S[i].v=S[i-1].v+x,S[i].c=i;
	sort(S,S+n+1,cmp);
	while(T--)scanf("%lld",&x),Work();
}