算法分析

题目给定多项式中每一项的指数和系数，对多项式进行相加，例如$(3x^2 + 2x^3) + (x^2 + x) = x + 4x^2 + 2x^3$

• 1、开一个p[]数组，p[i]存储的是指数是i的系数是p[i]
• 2、每次读入指数b和系数a时，p[b] += a
• 3、输出A + B结果，从大到小输出每一项的指数和系数

时间复杂度 $O(n + m)$

参考文献

pat

C++ 代码

#include <cstdio>
#include <iostream>

using namespace std;

double p[1010];

int main()
{
    int n,m;
    cin >> n;
    for(int i = 0;i < n;i ++)
    {
        int b;//指数
        double a;//系数
        cin >> b >> a;
        p[b] += a;
    }
    cin >> m;
    for(int i = 0;i < m;i ++)
    {
        int b;
        double a;
        cin >> b >> a;
        p[b] += a;
    }
    int k = 0;
    for(int i = 0;i <= 1000;i ++)
        if(p[i] != 0)
            k ++;

    cout << k ;
    for(int i = 1000;i >= 0;i --)
    {
        if(p[i] != 0)
        {
            printf(" %d %.1lf",i,p[i]);
        }
    }

    return 0;
}