題目翻譯 現在，你需要求出A，B兩個多項式的相加結果。 輸入要求 每一個輸入文件包含一個測試樣例。每一個樣例占兩行並且每行包含多項式的信息: $K\space N_1 \space a_{N_1}\space N_2 \space a_{N_2} \space ...\space N_k \spac ...
題目翻譯
現在，你需要求出A，B兩個多項式的相加結果。
輸入要求
每一個輸入文件包含一個測試樣例。每一個樣例占兩行並且每行包含多項式的信息:
\(K\space N_1 \space a_{N_1}\space N_2 \space a_{N_2} \space ...\space N_k \space a_{N_k}\)
這裡K代表多項式中非零項的數量，\(N_i\)和\(a_{N_i}\)(\(i\)=1,2,...,K)分別是指數(exponents)和繫數(coefficients)。\(1\leq K\leq 10\),\(0\leq N_K<...< N_2<N_1\leq1000\).
輸出要求
對於一個測試樣例，你需要在一行以相同格式輸出A和B的和。註意行尾沒有多餘的空格。請精確到小數點後一位。
樣例輸入
2 1 2.4 0 3.2
2 2 1.5 1 0.5
樣例輸出
3 2 1.5 1 2.9 0 3.2
分析：因為題上沒有說是按照從大到小的順序輸入的，並且在我經過測試後也發現輸入時指數的順序是混亂的。 所以我一開始的想法是建兩個鏈表，鏈表裡每個節點都是都存儲繫數和指數，然後把鏈表排序後再相加。但一想到要寫鏈表的排序演算法我就放棄了，而且代碼出錯的概率太高了。
之後在看過大佬的們的題解後，發現可以用類似桶排序的方法做。就是先開一個比指數的上限還要大的數組，裡面全都初始化成0，然後讀取一對指數和繫數，就把指數對應的項加上讀取繫數的值。之後先從小到大數一遍非0項的個數，再從大到小輸出即可。時間複雜度是\(O_{(n)}\)。
廢話不多說，直接上代碼。
#include <stdio.h>
#define KMAX 1001
float cof[KMAX];
int main()
{
int k;
scanf("%d", &k);
int e; //e和c分別用來臨時存儲讀取的指數和繫數
float c;
for (int i = 0; i < k; i++)
{
scanf("%d%f", &e, &c);
cof[e] = c;
}
scanf("%d", &k);
for (int i = 0; i < k; i++)
{
scanf("%d%f", &e, &c);
cof[e] += c; //註意這裡要用+=，因為A，B有相同的指數時，要加在一起
}
int cot = 0;
for (int i = 0; i < KMAX; i++) //先正序遍歷一遍，計算項的個數
if (cof[i] != 0)
cot++;
printf("%d", cot);
for (int i = KMAX - 1; i >= 0; i--) //最後倒序輸出
if (cof[i] != 0)
printf(" %d %.1f", i, cof[i]);
return 0;
}
