P3641 [APIO2016]最大差分

转载自洛谷本人题解

提供一个优秀一点的 $Subtask2$ 套路？

$Subtask1$

满足我们的查询次数不超过序列长的一半上取整

如果我们每次查询能够确定序列的两个位置，这道题就做完了

因为a序列是排好序的，所以我们会发现最大最小值一定是在开头和结尾处

而我们又不存在相同的元素，所以找到开头和结尾的值之后，每次查询 $Max-1$ 和 $Min+1$ 就可以知道次小值和次大值是什么

如此这样做下去，我们就能确定a序列了

会发现n为偶数时最后刚好查完，n为奇数时最后我们还要多一次查出单独的一个数，这也是为什么上取整

$Subtask$

本篇题解的核心思想：最优化剪枝

首先要观察到答案可以初步确定到 $(a_n-a_1)/n-1$

因为最坏情况下就是等差数列均匀分散

然后我们可以根据这个初步确定的答案去做出第一次询问：

$(a_1+1,a_1+ans)$

如果我们找到了数，你会发现不管找到了多少数，他们之间的差分都不可能作为新答案,因为那个差分一定小于当前设定的最小答案

所以我们把 $a_1$ 设置为 $max$ 值（要保证连续的两个做差），并继续下去

如果我们没有找到数，你会发现答案一定至少变大了1

因为下一个数至少是 $a_1+ans+1$ ,而他和 $a_1$ 的差是 $ans+1$

所以我们把最小答案设置成ans+1，并且下一次从上次的右端点+1开始查询即可

不过这样的找不到数过程可能会重复多次，最小答案限制也会变大多次，具体实现的细节可以看看代码

注意我们不要多次查询 $a_1$ 和 $a_n$

正确性....操作次数严格来讲是和数据有关的，不过最多可以卡到 $3 n-1$ ，再向上就卡不动了

比如：

2 6

1 2 3 4 5 7

最后说说如何调试本题吧

把题目中给出的两个函数复制粘贴到自己的代码中，然后给 $findgap$ 函数加上自己喜欢的参数
把给出的交互库复制粘贴到代码中，然后调整一下头文件等的位置
编写 $findgap$ ，之后按照交互库里的 $main$ 函数进行输入输出调试即可

AC code:



#include<bits/stdc++.h>
#define ll long long
using namespace std;
extern "C" void MinMax(long long, long long, long long *, long long *);

extern "C" long long findGap(int T, int n) {
	ll inf = 1e18;
	ll b_n, b_1,ans=0;
	if(T==1) {
		ll b_2,b_n2;
		MinMax(0,inf,&b_1,&b_n);
		n-=2;
		while(n>0) {
			MinMax(b_1+1,b_n-1,&b_2,&b_n2);
			n-=2;
			ans=max(ans,max(b_2-b_1,b_n-b_n2));
			b_1=b_2;
			b_n=b_n2;
		}
		ans=max(ans,b_n-b_1);
		return ans;
	}
	MinMax(0, inf, &b_1, &b_n);
	ll Lim = (b_n - b_1) / (n - 1);
	ll lst = b_1, tmp1 = 0, tmp2 = 0,R;
	for(ll L = b_1 + 1; L < b_n; L = R + 1) {
		R=min(L + Lim - 1, b_n - 1);
		MinMax(L, R, &tmp1, &tmp2);
		if(tmp1 == -1) {
			Lim=max(Lim,R-lst+1);
			continue;
		}
		ans = max(ans, tmp1 - lst);
		Lim= max(Lim,ans);
		lst = tmp2;
	}
	ans = max(ans, b_n - lst);
	return ans;
}

夏晓光(loveJY)的博客

P2157 [SDOI2009]学校食堂