题目描述

模拟多项式相加，相同指数时，系数相加

样例

2 1 2.4 0 3.2
2 2 1.5 1 0.5

3 2 1.5 1 2.9 0 3.2

算法1

(模拟，哈希) $O(nlgn)$

对于每个指数，直接使用哈希表做映射即可（unordered_map<int,double> mp;）

时间复杂度

需要对所有项排序，所以瓶颈在排序上

C++ 代码

#include <bits/stdc++.h>

using namespace std;

unordered_map<int,double> mp;

struct node {
    int a;
    double b;
};

bool cmp(node & a, node & b) {
    return a.a > b.a;
} 
vector<node> arr;

int main() {
//  freopen("in.txt", "r", stdin);

    int cnt;
    scanf("%d", &cnt);
    while (cnt --) {
        int a;
        double b;
        cin >> a >> b;
        mp[a] += b;
    }
    scanf("%d", &cnt);
    while (cnt --) {
        int a;
        double b;
        cin >> a >> b;
        mp[a] += b;
    }

    for (auto it = mp.begin(); it != mp.end(); it ++) {
        if (it->second != 0) // 特别注意这个对于系数为0的项，需要忽略，否则pat上只有17分
            arr.push_back({it->first, it->second});
    }

    sort(arr.begin(), arr.end(), cmp);

    cout << arr.size();

    for (int i = 0; i < arr.size(); ++ i) {
        printf(" %d %.1lf", arr[i].a, arr[i].b);
    }

    return 0;
}