P2118 比例簡化

題目描述

在社交媒體上，經(jīng)常會(huì)看到針對(duì)某一個(gè)觀點(diǎn)同意與否的民意調(diào)查以及結(jié)果。例如，對(duì)某一觀點(diǎn)表示支持的有1498 人，反對(duì)的有 902人，那么贊同與反對(duì)的比例可以簡單的記為1498:902。

不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大多數(shù)人肯定不會(huì)滿意。因?yàn)檫@個(gè)比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對(duì)于上面這個(gè)例子，如果把比例記為5:3，雖然與真實(shí)結(jié)果有一定的誤差，但依然能夠較為準(zhǔn)確地反映調(diào)查結(jié)果，同時(shí)也顯得比較直觀。

現(xiàn)給出支持人數(shù)A，反對(duì)人數(shù)B，以及一個(gè)上限L，請(qǐng)你將A比B化簡為A’比B’，要求在A’和B’均不大于L且A’和B’互質(zhì)（兩個(gè)整數(shù)的最大公約數(shù)是1）的前提下，A’/B’ ≥ A/B且A’/B’ - A/B的值盡可能小。

(本題目為2014NOIP普及T2)

輸入輸出格式

輸入格式：

?

輸入共一行，包含三個(gè)整數(shù)A，B，L，每兩個(gè)整數(shù)之間用一個(gè)空格隔開，分別表示支持人數(shù)、反對(duì)人數(shù)以及上限。

?

輸出格式：

?

輸出共一行，包含兩個(gè)整數(shù)A’，B’，中間用一個(gè)空格隔開，表示化簡后的比例。

?

輸入輸出樣例

輸入樣例#1：?復(fù)制 1498 902 10 輸出樣例#1：?復(fù)制 5 3

說明

對(duì)于100%的數(shù)據(jù)，1 ≤ A ≤ 1,000,000，1 ≤ B ≤ 1,000,000，1 ≤ L ≤ 100，A/B ≤ L。

?枚舉判斷

#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int a,b,A,B,L; double ans1,ans2,minn; int read() {int x=0,f=1; char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();return x*f; } int main() {A=read(),B=read(),L=read();ans1=1.0*A/B;minn=99999;for(int i=1;i<=L;i++)for(int j=1;j<=L;j++){ans2=1.0*i/j;if(ans2<ans1) break;if(ans2>=ans1&&ans2-ans1<minn) a=i,b=j,minn=ans2-ans1;} printf("%d %d",a,b);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/z360/p/7856123.html

總結(jié)

以上是生活随笔為你收集整理的洛谷——P2118 比例简化的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。