4159: [Neerc2009]Business Center

题目链接

题目大意：M部电梯，开始都在0层，第i部电梯每次可以上u_i层楼，或下d_i层楼，求第i部电梯这样上下n次后，这个电梯最低能停在哪层(最终要在1层或以上)。并取最小值输出。

题解：二分……据说有数学O(1)解法，然而并不会

我的收获：naive

#include <iostream> #include <cstdio> using namespace std; #define INF 0x3f3f3f3f int n,m,u,d,mx=INF; bool ok(int x){return x*u-(n-x)*d>=1;} void work() { int l=1,r=n,mid,ans; while(l<=r) { mid=(l+r)>>1;//上升mid次 if(ok(mid)) ans=mid*u-(n-mid)*d,r=mid-1; else l=mid+1; } mx=min(mx,ans); } void init(){ cin>>u>>d; } int main() { cin>>n>>m; while(m--){ init(); work(); } cout<<mx<<endl; return 0; }