题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=4159
二分每一个电梯上升的次数,然后在所有的电梯里取一个最小的就好了
上面的做法是我被某个萌萌的人蛊惑了心智
二分个蛋啊!
直接就可以求出来上升几次对于当前的电梯来说是最优的
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 |
#include<bits/stdc++.h> #define inf 2147483647 #define MAXN 2020 using namespace std; inline int rd(){ int x=0,y=1;char c=getchar(); while(c<'0' || c>'9'){if(c=='-')y=-y;c=getchar();} while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar(); return x*y; } int n,m,ans=inf; int main(){ n=rd(),m=rd(); for(int i=1; i<=m; i++){ int up=rd(),down=rd(); int x=(down*n)/(up+down)+1; ans=min(ans,up*x-down*(n-x)); } printf("%d\n",ans); return 0; } |
orz太神啦
太神啦
orz 太神了