• 周四. 4月 25th, 2024

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;
}

《[BZOJ1684][Usaco2005 Oct]Close Encounter》有一个想法
  1. Wow, amazing weblog layout! How long have you been running a blog for?
    you make blogging look easy. The overall look of your
    web site is great, as neatly as the content!

    You can see similar here sklep online

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注