PTA 1002 A+B for Polynomials

0
11

题目翻译

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

<

发布回复

请输入评论!
请输入你的名字