[CODEFORCES 1301B Motarack's Birthday](https://codeforces.com/contest/1301/problem/B)
=

## 題目大意
給定 $a$ 非負整數列，但有些值為 $-1$
需將 $-1$ 替換為非負整數 $k$ 使得 $m$ 最小

$m$ 為所有相鄰數的絕對差中最大值
例如 $a = (a_1, a_2, a_3)$
則 $m = \max(|a_1-a_2|, |a_2-a_3|)$

## 輸入
$a$ 數列
## 輸出
$m$ 及 $k$ (若 $k$ 有多個，任意輸出一個就好)

## 解法 1
觀察當 $a$ 長度為 $3$ 的情況 (因為足夠小 以便摸索解法)
如 $a = (x, -1, y)$

不失一般性的設 $x < y$
1. 若 $k \le x$ 則 $m \ge y-x$
2. 若 $k \ge y$ 則 $m \ge y-x$
3. 若 $x < k < y$ 則 $m = \max(k-x, y-k) < y-x$

所以要將 $k$ 落在 3. 的條件下才使 $m$ 盡量小

再細看 $x < k < y$
從 $k = x+1$ 遞增至 $y-1$
會發現 $k$ 與 $x$ 絕對差越來越大，而與 $y$ 絕對差越來越小
在這之中 $k$ 與 $x, y$ 的兩個絕對差會逐步至一個**最小對**，接著再增大
> $m$ 則從這對中找最大的那個

反之從 $k = y-1$ 遞減至 $x+1$ 也一樣

這貌似是個類似二次函數的凸函數 ($f: k \mapsto m$) (只有一個**局部極值**)
若是能證明任意長度的 $a$ 都有此函數特性，那麼可以用三分搜解決

不用管**不與 $k$ 相鄰的絕對差**，
因為不與 $k$ 相鄰的絕對差之中的最大值 $t$ 永遠都不會變動，也就是說若函數擁有理想上的特性，那麼 $m$ 在遞減時也只會降到 $t$。

而**與 $k$ 相鄰的絕對差**，也只需要關心最大值 $y$ 與最小值 $x$
因為若存在介於 $x, y$ 的數 $z$ 使得 $|k-z| > \max(|k-y|, |k-x|)$
則若 $k \ge z$ 得 $k > x$ (因 $x$ 是最小值)，但 $k-z > k-x \implies z < x$ 矛盾
或若 $k \le z$ 得 $k < y$ (因 $y$ 是最大值)，但 $z-k > y-k \implies z > y$ 矛盾
> $|k-z|$ 帶絕對值，所以要拆兩狀況論證

也就是說，任意長度的 $a$ 可類比為長度 $3$ 的情況

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e5 + 10;

int t, n;
vector<int> a;

int m(int k) {
  vector<int> b(a);
  int mx = 0; // maximum of absolute differences

  for(int i = 0; i+1 < n; i++) {
    if(b[ i ] == -1) b[ i ] = k;
    if(b[i+1] == -1) b[i+1] = k;

    mx = max(mx, abs(b[i] - b[i+1]));
  }

  return mx;
}

int main()
{
  scanf("%d", &t);

  while(t--) {
    scanf("%d", &n);

    a.resize(n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    int l = 0, r = 1e9+10;
    while(r - l > 2) {
      int k1 = l + (r-l)/3, k2 = r - (r-l)/3;
      if(m(k1) > m(k2)) l = k1;
      else r = k2;
    }

    if(m(l) < m(l+1)) printf("%d %d\n", m(l), l);
    else printf("%d %d\n", m(l+1), l+1);
  }

  return 0;
}

## 解法 2
將題目稍微**變形**一下
不去看相鄰對，而是給定 $a$ 非負數列 (不含 $-1$)，找到 $k$ 使每個數與 $k$ 的差中最大值最小化
明顯的，$k = {\min(a)+\max(a)\over2}$
> 解法 1 沒有給出 $k$ 應為多少

回到**原問題**，就是要把 $-1$ 相鄰的非負數抓出來算出 $k$

#include<bits/stdc++.h>
using namespace std;

int const maxn = 1e5 + 10;

int t, n, a[maxn];

int main()
{
  scanf("%d", &t);
  
  while(t--) {
    scanf("%d", &n);
    for(int i = 0; i < n; i++) scanf("%d", &a[i]);

    int mx = 0, mi = 1e9;
    for(int i = 0; i < n; i++) {
      bool c1 = i >  0  && a[i-1] == -1 && a[i] != -1;
      bool c2 = i < n-1 && a[i+1] == -1 && a[i] != -1;

      if(c1 || c2) mx = max(mx, a[i]), mi = min(mi, a[i]);
    }

    int m = 0, k = (mx+mi)/2;
    for(int i = 0; i < n; i++) if(a[i] == -1) a[i] = k;
    for(int i = 0; i+1 < n; i++) m = max(m, abs(a[i]-a[i+1]));

    printf("%d %d\n", m, k);
  }

  return 0;
}