题解 | 求两个多项式的和

利用归并排序思想，随后逆序输出

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <map>
using namespace std;

int main() {
    int n, m;
    map<int, int> mp1, mp2; // 键代表次方，值代表前面的系数，升序排列
    scanf("%d", &n);
    int a, b;
    for (int i = 0; i < n; i++) {
        scanf("%d%d", &a, &b);
        mp1[b] = a;
    }
    scanf("%d", &m);
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &a, &b);
        mp2[b] = a;
    }
    // 利用归并排序的思想将相同次方的项合并，合并到新的map中
    map<int, int> ans;
    auto it1 = mp1.begin();
    auto it2 = mp2.begin();
    while (it1 != mp1.end() && it2 != mp2.end()) {
        if (it1->first == it2->first) {
            ans[it1->first] = it1->second + it2->second;
            it1++;
            it2++;
        }
        else if (it1->first < it2->first) {
            ans[it1->first] = it1->second;
            it1++;
        }
        else if (it1->first > it2->first) {
            ans[it2->first] = it2->second;
            it2++;
        }
    }
    // 将剩余键值对直接插入到ans中
    while (it1 != mp1.end()) {
        ans[it1->first] = it1->second;
        it1++;
    }
    while (it2 != mp2.end()) {
        ans[it2->first] = it2->second;
        it2++;
    }
    // 按降次顺序输出
    for (auto iter = ans.rbegin(); iter != ans.rend(); ++iter) {
        if (iter->second == 0) continue; // 系数为0无需输出
        printf("%d %d ", iter->second, iter->first);
    }
    printf("\n");
    return 0;
}