自动搬运

查看原文

来自洛谷，原作者为

	Little09 「按照我们原来的期待 去证明我们的未来」

搬运于2025-08-24 22:49:59，当前版本为作者最后更新于2023-09-06 19:49:43，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

别写二分加神秘优化了。

定义 $b_i=a_i-a_{i-1}$。直接询问 $(i,i+1)$ 和 $(i-1,i+1)$。考虑第一种询问可以得知 $|a_i-a_{i+1}|$，也就是 $|b_{i+1}|$。

第二种询问能得到的是 $|b_i+b_{i+1}|$。考虑 $b_i,b_{i+1}$ 正负号相同，当且仅当 $|b_i+b_{i+1}|=|b_i|+|b_{i+1}|$。所以可以得知 $b_i,b_{i+1}$ 正负号是否相同。所有询问结束后，如果已知 $b_2$ 的正负号，就可以得知所有 $b$ 的正负号。

枚举 $b_2$ 的正负号，我们就可以得知 $a_i-a_1$ 的值，那么找到最小值就是 $1$，其他也就能算出来了。但是需要满足最小值的下标小于最大值的下标，如果不满足就改变 $b_2$ 的正负号即可。

询问次数 $2n-3$。

const int N=5005;
int a[N],b[N],c[N];

void solve(int n)
{
	rep(i,1,n-1) a[i]=query(i,i+1);
	c[2]=1;
	rep(i,1,n-2)
	{
		int w=query(i,i+2);
		if (w==a[i]+a[i+1]) b[i]=0;
		else b[i]=1;
	}
	rep(i,2,n-1)
	{
		if (b[i-1]==1) c[i+1]=-c[i];
		else c[i+1]=c[i];
	}
	rep(i,2,n) c[i]*=a[i-1];
	rep(i,2,n) c[i]+=c[i-1];
	int mnpos=1,mxpos=1;
	rep(i,2,n) if (c[i]<c[mnpos]) mnpos=i;
	rep(i,2,n) if (c[i]>c[mxpos]) mxpos=i;
	if (mxpos<mnpos) 
	{
		rep(i,1,n) c[i]*=-1;
		swap(mxpos,mnpos);
	}
	rep(i,1,n) if (i!=mnpos) c[i]-=c[mnpos];
	c[mnpos]=0;
	rep(i,1,n) answer(i,c[i]+1);
}