欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

PTA 1002 A+B for Polynomials

程序员文章站 2022-07-01 15:50:08
题目翻译 现在,你需要求出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;
}