• 周日. 9月 25th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[BZOJ1684][Usaco2005 Oct]Close Encounter

admin

11月 28, 2021

题目链接:

BZOJ1684.

一个小坑题。。

设需要求(frac cdsimfrac ab),那么可以枚举(c),算出(d)四舍五入。

同时需要保证(d)([1,32767])内。

(frac cd=frac ab),那么需取(d-1)(d+1)进行更新。

时间复杂度 (O(32767log_232767))

代码:

#include <cmath>
#include <cstdio>
#include <algorithm>

int Gcd(int a,int b){return b?Gcd(b,a%b):a;}
int a,b,g,s1,s2;
double ms=1e9;

void Check(int c,int d,int g)//用c/d更新答案,GCD为g
{
	double df=std::abs((double)a/b-(double)c/d);
	if(df<ms)s1=c/g,s2=d/g,ms=df;
}

int main()
{
	scanf("%d%d",&a,&b);
	for(int c=1;c<=32767;++c)
	{
		int d=(int)round((double)c*b/a);
		d=std::max(d,1),d=std::min(d,32767),g=Gcd(c,d);
		if(c/g==a&&d/g==b)//与原来的分数相等
		{
			if(d<32767)Check(c,d+1,Gcd(c,d+1));
			if(d>1)Check(c,d-1,Gcd(c,d-1));
		}
		else Check(c,d,g);
	}
	return printf("%d %d
",s1,s2),0;
}

发表回复

您的电子邮箱地址不会被公开。