PTA 1002 A+B for Polynomials

题目翻译

现在，你需要求出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;
}