st_nec's Blog

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

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

#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)\)就好啦。