题目大意：
给你n个数，有些数是未知的，要求给未知数的赋值，使得相邻两个数的最大绝对值最小。

思路：
本题可以三分。

 

 1 #include<bits/stdc++.h>
 2 using namespace std;  
 3 int const N=2e5+10;  
 4 int a[N],n,t;  
 5 int calc(int mid){
 6     int ret=0;  
 7     for(int i=1;i<n;i++)  
 8         if(a[i]==-1 && a[i+1]!=-1)  
 9             ret=max(ret,abs(mid-a[i+1])); 
10         else if(a[i]!=-1 && a[i+1]==-1)
11             ret=max(ret,abs(mid-a[i]));  
12         else if(a[i]!=-1 && a[i+1]!=-1)  
13             ret=max(ret,(int)abs(a[i]-a[i+1]));  
14     return ret;  
15 }
16 int main(){
17     scanf("%d",&t); 
18     while (t--){
19         scanf("%d",&n); 
20         for(int i=1;i<=n;i++) 
21             scanf("%d",&a[i]); 
22         int l=0,r=1e9;  
23         while (l<r-10){
24             int mid1=l+(r-l)/3;    
25             int mid2=l+(r-l)/3*2;  
26             int t1=calc(mid1);  
27             int t2=calc(mid2);  
28             if(t1>=t2) 
29                 l=mid1;     
30             else  
31                 r=mid2;  
32         }
33         int ans=1e9+10,x; 
34         for(int i=l;i<=r;i++){
35             int t=calc(i);  
36             if(t<ans)  
37                 ans=t,x=i;  
38         }
39         cout<<ans<<" "<<x<<endl;  
40     }
41     return 0; 
42 }

View Code