SRM 325 Div1 Medium ModularInequality

問題

数列Aと整数Pが与えられる。を満たす整数Xの個数を求めよ。

やりかた

数列の中央値に近い部分をXとすると題意の和は最も小さくなり、中央値から離れると和は大きくなっていく。式を満たすXは中央値付近でひとつづきに現れるので、これらの内の最大値と最小値が求まれば、この間の整数の個数が答えになる。
これらは両方共二分探索で求めることができる。

class ModularInequality {
public:
  vector<int> AA;
  ll labs(ll a){
    if(a > 0) return a;
    else return -a;
  }
  ll diff(ll a){
    ll sum = 0LL;
    for(int i = 0; i < (int)AA.size(); i++) sum += labs(AA[i] - a);
    return sum;
  }
  int countSolutions(vector <int> A, int P){
    sort(ALL(A));
    int N = A.size();
    AA = A;

    ll median = A[A.size() / 2];

    //式を満たす最小のXを求める
    ll ub = median + 1, lb = -LLINF;
    while(ub - lb > 1LL){
      ll mid = (ub + lb) / 2;
      if(diff(mid) > P) lb = mid;
      else ub = mid;
    }    
    ll left;
    for(left = ub - 100; left <= ub + 100; left++) //厳密な値を求める。とりあえず。。。
      if(diff(left) <= P) break;

    //式を満たす最大のXを求める
    ub = LLINF, lb = median - 1;
    while(ub - lb > 1LL){
      ll mid = (ub + lb) / 2;
      if(diff(mid) > P) ub = mid;
      else lb = mid;
    }
    ll right;
    for(right = ub + 100; right >= ub - 100; right--)
      if(diff(right) <= P) break;

    cout << left << " " << right << endl;
    return right < left ? 0 : right - left + 1;
  }
}