【POJ 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を二分探索した。