題目翻譯
現在，你需要求出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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/36261.html
標籤：C++
上一篇：2020年04月19日個人賽
下一篇：C++ 函式模板