AT2140题解

猜一猜我是谁 · 2022-07-02 20:02:31 · 题解

思路

这道题翻译有问题，不过楼上已经说了正确的翻译，所以这里就不再赘述了。

显然，要使票数总和最小，肯定先要两个人的得票数最小。所以我们可以设两个变量 u,v 作为目前两个人的得票数然后在每一步中满足 u:v=T_i:A_i。

先把 u 和 v 都分别变成 T_i 和 A_i 的倍数。因为题目要求票数不会减少，所以 u 和 v 应变为大于它们的最小的 T_i 或 A_i 的倍数。所以这一步要 u=T_i\times\left\lceil\dfrac{u}{T_i}\right\rceil,v=A_i\times\left\lceil\dfrac{v}{A_i}\right\rceil（注：表示 \left\lceil\dfrac{u}{T_i}\right\rceil 方法是：(u-1)/T_i+1，细想一下就能明白）。

接着比较 \dfrac{u}{T_i} 和 \dfrac{v}{A_i} 的大小。如果第一个小，那么说明 \dfrac{u}{T_i} 的比值小，根据比例的基本性质，u=\dfrac{v\times T_i}{A_i}。否则，同理 v=\dfrac{u\times A_i}{T_i}。

最后的答案即 u+v。

代码

#include<bits/stdc++.h>
using namespace std;
long long n,t[1005],a[1005];
long long ceilll(long long u,long long v){//计算向上取整
    return (u-1)/v+1;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++) cin>>t[i]>>a[i];
    long long u=t[1],v=a[1];//先赋值为两人第一次的得票数
    for(int i=2;i<=n;i++){
        u=t[i]*ceilll(u,t[i]);v=a[i]*ceilll(v,a[i]);//把 u 和 v 分别变成大于它们的最小的 t[i] 和 a[i] 的倍数
        if(u/t[i]<v/a[i]) u=v/a[i]*t[i];
        else v=u/t[i]*a[i];
    }
    cout<<(u+v)<<endl;
}