首页 > 代码库 > bzoj1684[Usaco2005 Oct]Close Encounter*
bzoj1684[Usaco2005 Oct]Close Encounter*
bzoj1684[Usaco2005 Oct]Close Encounter
题意:
找一个分数它最接近给出一个分数。你要找的分数的分子分母的范围在1..32767。
题解:
枚举所求分数的分子,用其乘上给出分数得到一个浮点数分母,比较分母向上/下取整所得分数与答案比较。
代码:
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <cmath> 5 #define inc(i,j,k) for(int i=j;i<=k;i++) 6 #define maxn 10010 7 using namespace std; 8 9 inline int read(){ 10 char ch=getchar(); int f=1,x=0; 11 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1; ch=getchar();} 12 while(ch>=‘0‘&&ch<=‘9‘)x=x*10+ch-‘0‘,ch=getchar(); 13 return f*x; 14 } 15 int n,d,ansa,ansb; double ans; 16 int main(){ 17 n=read(); d=read(); ans=10; 18 inc(i,1,32767){ 19 int j=n*i/d,k=j+1; 20 if(fabs((double)k/(double)i-(double)n/(double)d)<ans) 21 ans=fabs((double)k/(double)i-(double)n/(double)d),ansa=k,ansb=i; 22 if(j*d!=n*i&&fabs((double)j/(double)i-(double)n/(double)d)<ans) 23 ans=fabs((double)j/(double)i-(double)n/(double)d),ansa=j,ansb=i; 24 } 25 printf("%d %d",ansa,ansb); return 0; 26 }
20160927
bzoj1684[Usaco2005 Oct]Close Encounter*
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。