题解 P3641 【[APIO2016]最大差分】

· · 题解

这题我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;
}