Sengxian's Blog

描述

有 $n(2\le n\le 100000)$ 个严格递增的非负整数 $a_1, a_2, a_3,...,a_n$（$1\le a_i\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$）中的最大值。
你的函数 findGap 可以调用系统提供的查询函数 MinMax(s, t, &mn, &mx)，该函数的前两个参数 $s$ 和 $t$ 是 long long 类型的整数，后两个参数 &mn 和 &mx 是 long long 类型的整数的指针 （ 和 是 long long 类型的整数）。当 MinMax(s, t, &mn, &mx) 返回时，变量 将会存储满足 $a_i \in [s, t]$ 中的最小值，变量 将会存储满足 $a_i \in [s, t]$ 的最大值。如果区间中没有序列中的数，则 和 都将存储 -1。在查询时需要满足 $s\le t$，否则程序将会终止，该测试点计为 0 分。

分析

子任务1（30分）：
询问次数 $m \le \frac{n+1}{2}$。
方法：

1. 询问 $[0,{10}^{18}]$，得到最小值 $s_1$，最大值 $t_1$。
2. 询问 $[t_1+1,s_1-1]$，得到次小值 $s_2$，次大值 $t_2$。
   …

每次得到 $2$ 个值，$\frac{n+1}{2}$ 次以后得到了所有数，扫一遍出解。

子任务2（70分）：
每次询问的代价是：区间覆盖的序列中的数的个数 $+1$。
要求代价总和 $m \le 3n$。
先用 $n + 1$ 的代价找到序列的最小值 ，最大值 ，令 $L = \left\lceil \frac{\mathrm{mx} - \mathrm{mn}}{n} \right\rceil$，由鸽笼原理可知，最大的 $a_{i + 1} - a_i$（$1\le i\le n - 1$），大于等于 $L$，因为最坏的情况就是两两间隔相等，答案是 $\frac{\mathrm{mx} - \mathrm{mn}}{n - 1}$，显然大于等于 $L$。
我们将 这个区间以 $L$ 为大小分块，用当前块的最小值减去上一个有值块的最大值来更新答案（他们俩一定是相邻元素）；一个个块的推进，做到序列结尾，答案统计完毕。
分块后询问不超过 $n$ 次，只有 $n - 2$ 个点被统计，算上一开始的 $n + 1$，代价是：

可能会关心的几个问题：
Q: 为什么不用当前块的最大值减去当前块的最小值更新答案呢，在块中间的值都不管了吗?
A: 在同一块中更新答案没有意义，因为既不能保证相邻，而且相减得到的值不会大于 $L$。
Q: 这个方法一定能得到最大值吗？
A：为什么不能？由于答案大于等于 $L$，而所有大于等于 $L$ 的间隙全部被统计到了。

代码

//  Created by Sengxian on 5/11/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  APIO 2016 T3 鸽笼原理 + 分块
#include <bits/stdc++.h>
#include "gap.h"
using namespace std;

typedef long long ll;
ll findGap(int t, int n) {
    ll mn, mx, ans = 0;
    MinMax(0, 1e18 + 1, &mn, &mx);
    if (t == 1) {
        ll a[100000 + 3], l = mn, r = mx;
        a[1] = mn, a[n] = mx;
        for (int i = 2; i <= (n + 1) / 2; ++i) {
            MinMax(l + 1, r - 1, &mn, &mx);
            a[i] = mn, a[n - i + 1] = mx;
            l = mn, r = mx;
        }
        for (int i = 1; i < n; ++i) ans = max(ans, a[i + 1] - a[i]);
    } else {
        ll L = (mx - mn + n - 1) / n, last = mn;
        for (ll i = 0, l = mn + 1, r = mn + 1 + L; i < n; ++i, l += L, r += L) {
            r = min(r, mx - 1);
            if (l > r) break;
            ll mmn, mmx;
            MinMax(l, r, &mmn, &mmx);
            if (mmn != -1) {
                ans = max(ans, mmn - last);
                last = mmx;
            }
        }
        ans = max(ans, mx - last); //别忘了更新最后一个
    }
    return ans;
}