自动搬运

查看原文

来自洛谷，原作者为

	Taduro 失落映衬黑暗，火焰燃尽光明

搬运于2025-08-24 21:51:06，当前版本为作者最后更新于2019-07-16 14:27:35，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这题我UOJ上AC了，来洛谷发题解是为了水社区分。

uoj#206

子任务1（30分）

就是送的啊，会读题就会做。

先$MinMax(0,1e18,a_1,a_n)$你就知道了$a_1$和$a_n$，之后$MinMax(a_1+1,a_n-1,a_2,a_{n-1})$。。。。

这样问$\frac{n+1}{2}$次你就知道了整个序列。

子任务2（70分）

我们这次还是先问出$a_1$和$a_n$，然后考虑一下答案的最小值，就是中间n-2个数均匀分配。

这时答案最小是$\frac{a_n-a_1}{n-1}$，如果把序列分块，每块大小是$\frac{a_n-a_1}{n-1}$的话，很显然块内不会有答案。

那么我们就可以把每个块都问一遍，答案只会出现在当前块的最小值和上一个有值的块的最大值。

这样的话，第一次讯问对k的贡献是n+1，中间对k的贡献是$n-1+n-2$，意思是问了$n-1$次，出现了$n-2$个点。所以加起来最坏是$3n-2$。

#include "gap.h"
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
ll a[100011];
long long findGap(int T, int N){
	ll ans=0;int n=N;
if (T==1){
	a[0]=-1; a[n+1]=1LL*1000000000000000010;
	for (int i=1; i<=(n+1)>>1; i++)
		MinMax(a[i-1]+1,a[n-i+2]-1,&a[i],&a[n-i+1]);
	for (int i=1; i<n; i++)
		ans=max(ans,a[i+1]-a[i]);
}
else{
	ll minn,maxn,l,r,k,rl,las=-1;
	MinMax(0,1LL*1000000000000000000,&minn,&maxn);
	k=(maxn-minn)/(n-1); las=minn;
	if ((maxn-minn)%(n-1)) k++;
	for (ll i=minn+1; i<maxn; i+=k){
		rl=min(i+k-1,maxn-1);
		MinMax(i,rl,&l,&r);
		ans=max(ans,l-las);
		if (r>0) las=r;
	}
	ans=max(ans,maxn-las);
}
	return ans;
}