7
6
2015
0

bzoj 4159: [Neerc2009]Business Center

先粘上一道水题的题解撑撑门面。

这简直太水了,二分一下上楼的次数,没啥好说的,直接上代码。

#include<cstdio>
#include<algorithm>
#define inf 0x7fffffff
using namespace std;

int n,m,mx,u,d;

int main(){
	scanf("%d%d",&n,&m);
	mx=inf;
	while(m--){
		scanf("%d%d",&u,&d);
		int l=1,r=n;
		while(l<=r){
			int mid=(l+r)>>1;
			if((mid*u)-((n-mid)*d)<=0){
				l=mid+1;
			}else{
				mx=min(mx,(mid*u)-((n-mid)*d));
				if(l==r)	break; 
				r=mid;
			}
		}
	}
	printf("%d\n",mx);
	return 0;
}

据说还有一种很神的数学法,O(1)秒出,我大概写一下:

解如下方程组:

\(u*x+d*y=0\)

\(x+y=n\)

然后取一个\(ceil(x)\)就好啦。

Category: 二分 | Tags: bzoj 二分 数论 | Read Count: 409

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com