題目鏈接：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 }
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85171.html
標籤：其他
下一篇：復雜鏈表的復制