1009. Product of Polynomials.md

【PAT A-1009】Product of Polynomials

题意概述

计算两个多项式 A 和 B 的乘积。

输入输出格式

输入有两行，每行按格式$K\ N_1\ a_{N_1}\ N_2\ a_{N_2}\cdots N_K\ a_{N_k}$代表一个多项式，其中 K 代表多项式中非零项的系数，Ni 和 a{N_i}分别代表多项式项的次数和系数，次数由高到低排列。

按输入格式输出多项式 A 和 B 的乘积，项的系数保留一位小数。

数据规模

$$1\le K\le10,\ 0\le N_i\le1000$$

算法设计

同样，由于输出的次数也要从高到低排列，并且需要时刻查询次数对应的系数，我们可以用 map 存储次数和系数之间的对应关系，注意这里 map 要按键从大到小排序。先用一个 map 将读取的第一个多项式存储下来，然后在读取第二个多项式的过程中计算出乘积多项式的每一项存储到另一个 map 中。最后将加和的结果中系数为零的项删除。按要求输出结果即可。

注意点

如果两个多项式相加后所有系数均为零，应该只输出0，代表最后得到的乘积的项数为零，后面不能跟空格。

C++代码

#include <bits/stdc++.h>
using namespace std;
using gg = long long;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    map<gg, double, greater<gg>> pa, ans;  //按键从高到低排序
    gg ki, ai;
    double bi;
    cin >> ki;
    while (ki--) {  //读取并存储第一个多项式
        cin >> ai >> bi;
        pa[ai] = bi;
    }
    cin >> ki;
    while (ki--) {  //读取第二个多项式
        cin >> ai >> bi;
        for (auto& i : pa) {  //计算和的多项式
            ans[ai + i.first] += bi * i.second;
        }
    }
    for (auto i = ans.begin(); i != ans.end();) {  //删除和中系数为0的项
        if (i->second == 0) {
            i = ans.erase(i);
        } else {
            ++i;
        }
    }
    if (ans.empty()) {  //如果所有项系数均为0，只输出一个零即可
        cout << "0";
        return 0;
    }
    cout << fixed << setprecision(1);  //浮点数保留一位小数
    cout << ans.size();
    for (auto& i : ans) {
        cout << " " << i.first << " " << i.second;
    }
    return 0;
}