日々精進

aikoと旅行とプログラミング

【POJ 3863】Business Center

問題

3863 -- Business Center

ソースコード

#include <iostream>
#include <cmath>
#include <limits>

#define rep(i,n) for(int i = 0 ; i < n ; i++)

using namespace std;

int n, m;

int solve(int u, int d){
  int left = 0, right = n+1;
  int ans = numeric_limits<int>::max();
  int mid, rank;

  while(left < right){
    mid = (left + right) / 2;
    rank = u*mid - d*(n-mid);
    if(rank <= 0) left = mid+1;
    else{
      right=mid;
      if(ans > rank) ans = rank;
    }
  }

  return ans;
}

int main(){
  int ans = numeric_limits<int>::max();
  cin >> n >> m;
  rep(i,m){
    int u, d;
    cin >> u >> d;
    ans = min(ans,solve(u,d));
  }
  cout << ans << endl;
}

条件を満たすnを二分探索した。