「APIO 2016」Gap

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：UOJ 206

这是一道交互题。

有 $n$ 个严格递增的非负整数 $a_1,a_2,\dots,a_n$（$0\le a_1<a_2<\dots<a_n\le 10^{18}$）。你需要找出 $a_{i+1}−a_i$（$1\le i\le n-1$）里的最大的值。

你的程序不能直接读入这个整数序列，但是你可以通过给定的函数来查询该序列的信息。关于查询函数的细节，请根据你所使用的语言，参考下面的实现细节部分。

你需要实现一个函数，该函数返回 $a_{i+1}−a_i$（$1\le i\le n-1$）中的最大值。

实现细节（C/C++）

你需要包含头文件 gap.h。

你需要实现一个函数 $\text{findGap}(T,N)$，该函数接受下面的参数，并返回一个 $\text{long long}$ 类型的整数：

  • $T$：子任务的编号（$1$ 或者 $2​$）
  • $N​$：序列的长度

你的函数 $\text{findGap}$ 可以调用系统提供的查询函数 $\text{MinMax}(s,t,\&mn,\&mx)$，该函数的前两个参数 $s$ 和 $t$ 是 $\text{long long}$ 类型的整数，后两个参数 $\&mn$ 和 $\&mx$ 是 $\text{long long}$ 类型的整数的指针（$mn$ 和 $mx$ 是 $\text{long long}$ 类型的整数）。当 $\text{MinMax}(s,t,\&mn,\&mx)$ 返回时，变量 $mn$ 将会存储满足 $a_i\in [s,t]$ 中 $a_i$ 的最小值，变量 $mx$ 将会存储满足 $a_i\in[s,t]$ 中 $a_i$ 的最大值。如果区间 $[s,t]$ 中没有序列中的数，则 $mn$ 和 $mx$ 都将存储 $-1$。在查询时需要满足 $s\le t$，否则程序将会终止，该测试点计为 $0$ 分。

限制与约定

对于所有的测试点，有 $2\le n\le 10^5$。

每一个测试点开始测试之前，$M​$ 都将被初始化为 $0​$。

子任务 $1$（$30$ 分）：每一次调用 $\text{MinMax}$ 都将使 $M$ 加 $1$。为了获得所有分数，需要满足对于该子任务下的所有测试点，都有 $M\le \frac{n+1}{2}$。

子任务 $2$（$70$ 分）：定义 $k$ 为调用 $\text{MinMax}$ 时，区间 $[s,t]$ 中的序列中数的数量。每次调用 $\text{MinMax}$，将使 $M$ 加上 $k+1$。对于每一个测试点，如果 $M\le 3n$，你将得到 $70$ 分，否则将得到 $\frac{60}{\sqrt{\frac{M}{n}+1}-1}$ 分。你的该子任务的得分是其下所有测试点中的最低分。

下载

样例及测评库下载

Solution

子任务 1

由于有 $0\le a_1<a_2<\dots<a_n\le 10^{18}$ 这个限制，我们可以从两头向中间询问，第一次询问 $[0,10^{18}]$ 得到 $a_1,a_n$ 的值，接下来询问 $[a_1+1,a_n-1]$ 得到 $a_2,a_{n-1}$ 的值……以此类推，我们可以发现询问次数恰好是 $\frac{n+1}{2}​$，可以通过本子任务。

子任务 2

我们先确定答案的下界：设 $s,t$ 为询问 $[0,10^{18}]$ 得到的结果，那么通过鸽巢原理可以得到答案的下界为 $\left\lfloor\frac{t-s}{n-1}\right\rfloor$，记为 $p$（两个数之间的最大间隔最少为 $p$）。这样一来，我们就只关心那些长度为 $p+1$ 的区间了。

设当前询问的区间为 $[l,r]$（初始值 $l=s+1$，且显然有 $r=l+p$），得到的结果为 $mn,mx$（当 $mn=-1,mx=-1$ 时忽略这个区间）；那么我们用 $mn-\text{上一个出现的数字}$ 来更新答案，并将 $\text{上一个出现的数字}$ 设为 $mx$。接下来询问区间 $[l’,r’]$（其中 $l’=r+1,r’=l’+p$），不断更新答案直到 $l>t$ 为止。

最后证明一下 $M\le 3n$。第一次询问得到 $[s,t]$ 后 $k=n$，接下来不超过 $n-1$ 次询问，总共包含不超过 $n$ 个点，故 $M\le (n+1)+(n-1)+n\le 3n$，符合条件。

时间复杂度：$O(n)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
 
#include <cstdio>
#include <algorithm>
#include "gap.h"

const int N=1e5+5;
long long a[N];

long long findGap(int T,int n) {
    long long ans=0;
    if(T==1) {
        long long s=0,t=1e18;
        for(int l=1,r=n;l<=r;++l,--r) MinMax(s,t,&a[l],&a[r]),s=a[l]+1,t=a[r]-1;
        for(int i=2;i<=n;++i) ans=std::max(ans,a[i]-a[i-1]);
    } else {
        long long s,t;
        MinMax(0,1e18,&s,&t);
        long long p=(t-s)/(n-1),pre=s;
        for(long long i=s+1;i<=t;i+=p+1) {
            long long mn,mx;
            MinMax(i,i+p,&mn,&mx);
            if(~mn) ans=std::max(ans,mn-pre),pre=mx;
        }
    }
    return ans;
}
0%