題目來源

PTA 團體程式設計天梯賽-練習集 L1-009 N個數求和 (20分)

https://pintia.cn/problem-sets/994805046380707840/problems/994805133597065216

題目描述

本題的要求很簡單，就是求N個數字的和。麻煩的是，這些數字是以有理數分子/分母的形式給出的，你輸出的和也必須是有理數的形式。

輸入格式：

輸入第一行給出一個正整數N（≤100）。隨後一行按格式a1/b1 a2/b2 ...給出N個有理數。題目保證所有分子和分母都在長整型範圍內。另外，負數的符號一定出現在分子前面。

輸出格式：

輸出上述數字和的最簡形式 —— 即將結果寫成整數部分 分數部分，其中分數部分寫成分子/分母，要求分子小於分母，且它們沒有公因數。如果結果的整數部分為0，則只輸出分數部分。

樣例：

輸入樣例1：

5
2/5 4/15 1/30 -2/60 8/3

輸出樣例1：

3 1/3

輸入樣例2：

2
4/3 2/3

輸出樣例2：

2

輸入樣例3：

3
1/3 -1/6 1/8

輸出樣例3：

7/24

思路

從題目“分子/分母”的輸入形式可以看出我們不能採用scanf和cin直接輸輸入值 而要採用字元輸入再轉換為數值

計算過程中判斷好符號 暴力通分直接加減即可

防止通分過程超出長整型範圍 最好每一步結果都約分

我最開始暴力約分來著 發現會超時 就用歐幾裡得演算法了 不麻煩也不會超時

輸出時註意題目要求的形式 想仔細一點每種條件怎麼輸出即可

代碼

 1 #include <cstdio>
 2 using namespace std;
 3 int n,o=1,oo; char x=1; //o-結果是否為非負數 oo-當前輸入的有理數是否為非負數
 4 long long p,q,f=0,g=1,c;
 5 inline long long read(); //快讀 由於分子分母間有‘/’分隔且分母一定是正數 標準快讀模板即可完成
 6 inline int yue(long long a,long long b);//求a和b的最大公約數
 7 int main()
 8 {
 9 　　scanf("%d",&n); 
10 　　for(int i=1;i<=n;i++)
11 　　{
12 　　　　while(!(x>=48&&x<=57)&&x!='-')
13 　　　　　　x=getchar();
14 　　　　if(x=='-') oo=0;
15 　　　　else    oo=1; //判斷當前輸入的有理數是否為非負數
16　　　　 p=read();
17 　　　　q=read(); //以“|p/q|”形式讀入當前有理數
18 　　　　p*=g;
19 　　　　f*=q;
20 　　　　g*=q; //暴力通分 本題數據範圍內沒有超出長整型
21 　　　　if((o&&oo)||(!o&&!oo)) //如果結果和當前輸入有理數同號 只要分子絕對值部分相加即可
22 　　　　　　f+=p;
23 　　　　else if(o&&!oo) //如果結果為正 當前輸入有理數為負 則需要比較結果與當前輸入有理數的大小來確定此次運算後結果的符號 
24 　　　　{
25 　　　　　　if(f>=p) //當前結果大於當前輸入有理數的絕對值 結果仍為正數 以下同理 
26 　　　　　　　　f-=p;
27 　　　　　　else
28 　　　　　　　　o=0,f=p-f;
29 　　　　}
30 　　　　else if(!o&&oo)
31 　　　　{
32 　　　　　　if(f>=p)
33 　　　　　　　　o=1,f-=p;
34 　　　　　　else
35 　　　　　　　　f=p-f;
36 　　　　}
37 　　　　int u=yue(f,g); //u為f和g的最大公約數
38 　　　　f/=u;
39 　　　　g/=u; //約分
40 　　}
41 　　if(o==0) printf("-"); //如果結果是負數 輸出負號
42　　 if(f==0)    printf("0"); //如果結果是0 輸出0
43 　　else if(f%g==0)    printf("%lld",f/g); //如果結果可以約分為整數
44 　　else if(g%f==0) printf("1/%lld",g/f);//如果結果可以約分為“1/x”形式
45 　　else if(f>g) //如果結果的分子大於分母 即結果為假分數 需要轉化為帶分數
46 　　{
47 　　　　printf("%lld ",f/g); //整數部分
48 　　　　f%=g;
49　　　　 printf("%lld/%lld",f,g); //分數部分
50 　　}
51 　　else
52　　　　 printf("%lld/%lld",f,g); //如果結果為真分數
53 　　return 0;
54 }
55 inline int yue(long long a,long long b) //歐幾裡得演算法 親測暴力約分會超時
56 {
57 　　if(a>b) c=a,a=b,b=c; 
58 　　while(a!=0) //
59 　　{
60 　　　　while(b>=a) //標準%運算比較慢 直接減
61 　　　　　　b-=a;
62 　　　　c=a,a=b,b=c;
63 　　}
64 　　return b;
65 }
66 inline long long read()
67 {
68 　　long long s=0;
69 　　while(!(x>=48&&x<=57))
70 　　　　x=getchar();
71 　　while(x>=48&&x<=57)
72 　　　　s*=10,s+=x-48,x=getchar();
73 　　return s;
74 }

吐槽

很少見到PTA這樣AC紅WA綠的平臺了 屬實清新脫俗:)