PAT Advanced 1002. A+B for Polynomials

1. Problem Description:

This time, you are supposed to find \(A+B\) where \(A\) and \(B\) are two polynomials.

2. Input Specification:

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

\(K\) \(N_1\) \(a_{N_1}\) \(N_2\) \(a_{N_2}\) \(...\) \(N_K\) \(a_{N_K}\)

where \(K\) is the number of nonzero terms in the polynomial, \(N_i\) and \(a_{N_i}\) (\(i=1,2,⋯,K\)) are the exponents and coefficients, respectively. It is given that \(1≤K≤10\)，\(0≤N_K<⋯<N_2<N_1≤1000\).

3. Output Specification:

For each test case you should output the sum of \(A\) and \(B\) in one line, with the same format as the input. Notice that there must be NO extra space at the end of each line. Please be accurate to 1 decimal place.

4. Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

5. Sample Output:

3 2 1.5 1 2.9 0 3.2

6. Performance Limit:

Code Size Limit
16 KB
Time Limit
400 ms
Memory Limit
64 MB

思路：

定义map<int, double>类型变量res存储两个多项式的和，多项式每一项的指数作为key，累加其系数即可，最后倒序遍历res进行输出。这里第一次提交时testpoint3，4，5，6报wrong answer，排查后发现忽略了系数为负数的情况，输出前需要将res中系数为0的元素进行删除，修改后AC。

参考大佬题解：1002. A+B for Polynomials (25)-PAT甲级真题_柳婼的博客-CSDN博客 ，其实根据指数 \(N_i\) 的上限维护一个数组即可，不过这里用map容器不用考虑内存分配还是很爽的。

My Code & Result:

#include <iostream>
#include <map>

using namespace std;

// first submit testpoint3, 4, 5, 6 wrong answer
int main(void)
{
    map<int, double> res;
    int termCount=0, tempInt=0;
    double tempDouble=0.0;
    int i=0; //iterator

    cin >> termCount;
    for(i=0; i<termCount; ++i)
    {
        cin >> tempInt >> tempDouble;
        res[tempInt] += tempDouble;
    }

    cin >> termCount;
    for(i=0; i<termCount; ++i)
    {
        cin >> tempInt >> tempDouble;
        res[tempInt] += tempDouble;
    }

    // coeffinet may be negative, cause some term in res be zero
    for(auto it=res.begin(); it!=res.end(); ) // erase the zero term, this fixed testpoint3, 4, 5, 6
    {
        if(it->second == 0)
        {
            it = res.erase(it);
        }
        else
        {
            ++it;
        }
    }
    
    
    cout << res.size();
    for(auto it=res.rbegin(); it!=res.rend(); ++it)
    {
        //cout << ' ' << it->first << ' ' << it->second;
        printf(" %d %.1lf", it->first, it->second);
    }
    cout << endl;

    return 0;
}

Compiler
C++ (g++)
Memory
440 / 65536 KB
Time
4 / 400 ms