题目链接：http://codeforces.com/problemset/problem/1301/B
思路：
（1）都是-1的情况
（2）只有一个除-1之外的数
（3）至少有两个除-1之外的不同的数字
对于（3），我们可以得出最大数字和最小数字_max,_min，而我们的答案m和k易得一定是在[_max,_min]中得出，
那么我们当然可以初始化m = (_max-_min)。因为数据范围大，我们可以通过二分来处理这个答案。
我们可以二分mid ∈[L=_min,R=_max]，枚举k，然后把k带入原数组，覆盖-1，在这个k的情况下，tmp_m最大是多少，
并且记录tmp_m最大的时候，两个坐标,dx,dy。为什么要记录两个坐标呢，因为我们不知道怎么二分才是最优的，
而我们可以想到,在一个一维坐标上，（x-----------mid--------y），“--"表示距离，dis(max(mid-x,y-mid)) = m,我们想的是
可不可以让m变小，那么我们可以让这个距离尽可能的平分，那么m就最小了。
显然：如果tmp_m<m那么更新m = tmp_m，k = mid。
这里有一种特殊情况（ -1 -1 -1 40 35 -1 35 ），m = (_max-_min)就是答案，所以一开始对k也要初始化一下，显然k = _max or _min都可。
1 #include <iostream> 2 #include <string> 3 #include <cstdio> 4 #include <algorithm> 5 #include <cmath> 6 using namespace std; 7 8 const int N = (int)2e5+100,inf = (int)1e9+100; 9 int a[N]; 10 int m,k,l,r,n,mid; 11 12 void fun(int mid){ 13 int dx,dy,inx_x,inx_y,tmp_m = -1; 14 for(int i = 1; i < n; ++i){ 15 if(a[i-1] == -1 && a[i] == -1) continue; 16 dy = a[i] == -1? mid : a[i]; 17 dx = a[i-1] == -1? mid : a[i-1]; 18 if(abs(dx-dy) > tmp_m){//tmp_m最大化 19 tmp_m = abs(dx-dy); 20 inx_x = i-1; inx_y = i;//坐标 21 } 22 } 23 int v = a[inx_x] == -1 ? a[inx_y] : a[inx_x]; 24 if(v >= mid) l = mid + 1;// x-------mid-----------v 25 else r = mid - 1; // v-----------mid------x 26 27 if(tmp_m < m){//m最小化 28 m = tmp_m; k = mid; 29 } 30 } 31 32 int main(){ 33 34 ios::sync_with_stdio(false); 35 cin.tie(0); cout.tie(0); 36 37 int T; 38 cin >> T; 39 while(T--){ 40 cin >> n; 41 int _min = inf,_max = -1; 42 for(int i = 0; i < n; ++i){ 43 cin >> a[i]; 44 if(a[i] == -1) continue; 45 _min = min(_min,a[i]); 46 _max = max(_max,a[i]); 47 } 48 49 if(_min == inf && _max == -1) cout << 0 << " " << 0 << endl; 50 else if(_max == _min) cout << 0 << " " << _min << endl; 51 else{ 52 l = _min,r = _max,mid,k = _min; 53 m = r-l; 54 while(l <= r){ 55 mid = (l+r)>>1; 56 fun(mid); 57 } 58 cout << m << " " << k << endl; 59 } 60 } 61 62 return 0; 63 }