題意
https://vjudge.net/problem/AtCoder-2140
每次告訴你新的a:b，計算最后最小的a+b，
思路
如
3 2 3 1 1 3 2
先令a=2,b=3，發現新的為1:1，那么用a/1,b/1，發現b/1=3更大，所以要盡可能滿足b（票數不能減少），所以就變成a=3,b=3，接著發現3：2，用a/3=1,b/2=1.5，同樣b大，但因為票數為整數，所以不能是4.5：3，而是用1.5向上取整計算，所以是6：4，
這題卡精度，要手寫向上取整函式才能過，
代碼
#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int N=200005;
const int mod=1e9+7;
const double eps=1e-8;
const double PI = acos(-1.0);
#define lowbit(x) (x&(-x))
ll ceils(ll x,ll y)
{
if(x%y==0)
return x/y;
return x/y+1;
}
int main()
{
std::ios::sync_with_stdio(false);
int n;
ll a,b;
cin>>n>>a>>b;
for(int i=1;i<n;i++)
{
ll x,y;
cin>>x>>y;
ll t=max(ceils(a,x),ceils(b,y));
a=x*t,b=y*t;
}
cout<<a+b<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/127161.html
標籤：其他