[APIO 2016] Gap：交互式，鸽笼原理

本文主要是介绍[APIO 2016] Gap：交互式，鸽笼原理，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

讨论闭幕式的时候，大家提议让YJQ神犇上台发表一番获奖感言，YJQ说，他想说两句话：1. T3是社区送温暖题。2. 在座的各位，除了我，都不是垃圾。

最后第一句话说没说我忘记了，第二句是说了的，引起全场唏嘘一片……

虽然没有奖，但还是很开心。那是第一次参加全国性的比赛，看到了许许多多来自祖国五湖四海的神犇。当了一回主持人（虽然台词很少，主要负责PPT），无论是写台词、一起讨论，还是彩排，都是美好的回忆。DZD主席坚持要 one by one 地颁奖，并且金银铜都颁，导致先前准备的游戏全部泡汤……看到NOI 2016给所有获奖选手一个一个颁奖，有不一样的感觉。

YJQ神犇的第二句显然是自谦QAQ 但第一句是真的……

考场上我拿了0分和30分。嗯，量子态。网络太差了，而且我是12点多钟开始写的这一题，直到离开考场的那一刻评测结果都没看到。再加上没有获奖，文件上找不到分数，也许这就是永远的谜了。

第一个子任务，对查询次数做出限制。两边夹，往中间收缩，即可还原出整个序列。

第二个子任务，限制查询次数和查到的数的总数。得换一个思路了。不再想着要还原出整个序列，而是从答案本身入手。我们能得出它的一个范围吗？可以，只要知道整个序列的首项和末项。鸽笼原理！假设答案小于 $\frac {a_N-a_1} {N-1}$ ，那么推出 $a_N - a_1 < a_N - a_1$ ，矛盾。因此，答案不小于 $ceiling(\frac {a_N-a_1} {N-1})$ 。 $a_2, a_3, \cdots, a_{N-1}$ 中，如果存在两项，差小于等于 $ceiling(\frac {a_N-a_1} {N-1})$ ，那么这两项之间的项（如果存在）对答案是没有贡献的。

答案也有一个上界： $a_N-a_1-N+2$ 。

听说这道题也可以用倍增来做。但是不知道怎么搞……搞清楚了再来补上。

放代码。第一次交挂成30分，数组开小，RE了。

#include "gap.h"
#include <algorithm>
using namespace std;
const int MAX_N = 100000;
typedef long long ll;
ll a[MAX_N*2];
long long findGap(int T, int N)
{ll ans = 1, s = 0, t = 1e18, mn, mx;int n = 0;if (T == 1) {ll head = 0, tail = N-1;while (head <= tail) {MinMax(s, t, &mn, &mx);a[head++] = mn;a[tail--] = mx;s = mn+1;t = mx-1;}n = N;} else {MinMax(s, t, &mn, &mx);ll d = (mx-mn+N-1)/N, x, y;a[n++] = mn;for (s = mn+1, t = s+d; s < mx; s = t+1, t = s+d) {MinMax(s, min(t, mx-1), &x, &y);if (x == -1)continue;a[n++] = x;a[n++] = y;}a[n++] = mx;}for (int i = 1; i < n; ++i)ans = max(ans, a[i] - a[i-1]);return ans;
}