Codeforces 1301B Motarack's Birthday（二分）

题目链接：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都可。

 #include <iostream>

 #include <string>

 #include <cstdio>

 #include <algorithm>

 #include <cmath>

 using namespace std;

 const int N = (int)2e5+,inf = (int)1e9+;

 int a[N];

 int m,k,l,r,n,mid;

 void fun(int mid){

     int dx,dy,inx_x,inx_y,tmp_m = -;

     for(int i = ; i < n; ++i){

         if(a[i-] == - && a[i] == -) continue;

         dy = a[i] == -? mid : a[i];

         dx = a[i-] == -? mid : a[i-];

         if(abs(dx-dy) > tmp_m){//tmp_m最大化

             tmp_m = abs(dx-dy);

             inx_x = i-; inx_y = i;//坐标

         }

     }

     int v = a[inx_x] == - ? a[inx_y] : a[inx_x];

     if(v >= mid) l = mid + ;// x-------mid-----------v

     else r = mid - ;       //  v-----------mid------x

     if(tmp_m < m){//m最小化

         m = tmp_m; k = mid;

     }

 }

 int main(){

     ios::sync_with_stdio(false);

     cin.tie(); cout.tie();

     int T;

     cin >> T;

     while(T--){

         cin >> n;

         int _min = inf,_max = -;

         for(int i = ; i < n; ++i){

             cin >> a[i];

             if(a[i] == -) continue;

             _min = min(_min,a[i]);

             _max = max(_max,a[i]);

         }

         if(_min == inf && _max == -) cout <<  << " " <<  << endl;

         else if(_max == _min) cout <<  << " " << _min << endl;

         else{

             l = _min,r = _max,mid,k = _min;

             m = r-l;

             while(l <= r){

                 mid = (l+r)>>;

                 fun(mid);

             }

             cout << m << " " << k << endl;

         }

     }

     return ;

 }

巴特西

Codeforces 1301B Motarack's Birthday（二分）

最新文章

热门文章