欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

atcoder046C - AtCoDeer and Election Report

程序员文章站 2022-07-14 10:34:15
...

题目:C - AtCoDeer and Election Report C-AtCoDeer
atcoder046C - AtCoDeer and Election Report
题意很明显,每次给出一个比例,要求两个数在不能减少的基础上,以为最小的变化形成这个比例.
思路:让上一次的 x,y:x/y=n*(a/b) (a,b就是题目中的T和A),这里需要求的是n最小能取多少。可以选择从1开始枚举直到n * a>=x&&n * b>=y但是这样做时间复杂度太高了,而且没必要.可以让n=max(x/a,y/b),再判断一下n * a与x大小,n * b与y的大小.

#include<iostream>
#include<algorithm>
typedef long long ll;
using namespace std;
int main()
{
	ll n,t,x=1,y=1;//x,y不为0
	cin>>t;
	while(t--)
	{
		ll a,b;
		cin>>a>>b;
		n=max(x/a,y/b);
		while(n*a<x||n*b<y)n++;
		x=a*n,y=b*n;
	}
	cout<<x+y<<"\n";
	return 0;
}

相关标签: AtCoder的一些刷题