P9599 [JOI Open 2018] 木琴

Little09 · 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);
}