题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4159
题意:M 部电梯,开始都在 0 层,第 i 部电梯每次可以上\(u_i\) 层楼,或下\(d_i\) 层楼,求第 i 部电梯这样上下 n 次后,这个电梯最低能停在哪层 (最终要在 1 层或以上)。并取最小值输出。
\(O(1)\) 的数学式子随便画画就出来了吧 T.T
解出来 x,加个 1 就可以啦,因为没有 0 层以下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <cstdio> #define N 100000 #define ll long long char xB[1<<15],*xS=xB,*xT=xB; #define getc() (xS==xT&&(xT=(xS=xB)+fread(xB,1,1<<15,stdin),xS==xT)?0:*xS++) inline int read() { int x=0,f=1;char ch=getc(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getc();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getc();} return x*f; } int n,m; int ans; int Mn(int a,int b) {return a<b?a:b;} int main() { n=read(),m=read(); ans=1000000000; while(m--) { int x=read(),y=read(); int tmp=(int)(n*y/(x+y))+1; ans=Mn(ans,tmp*x-(n-tmp)*y); } printf("%d\n",ans); } |
Comments | NOTHING