PAT-甲级 1002. A+B for Polynomials

2017-12-28

题目信息

题目

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

Input

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial: K N1 aN1 N2 aN2 ... NK aNK, where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1, 2, ..., K) are the exponents and coefficients, respectively. It is given that 1 <= K <= 10，0 <= NK < ... < N2 < N1 <=1000.

Output

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.

Sample Input

1 2	2 1 2.4 0 3.2 2 2 1.5 1 0.5

Sample Output

1	3 2 1.5 1 2.9 0 3.2

题目来源

1002. A+B for Polynomials

解题思路

思路分析

题为两个多项式相加，次数是逆序的，且没有负数，可以用map来映射，本题直接用的一个map，没有先用两个分别把输入存起来

或者也可以用单链表，然后类似归并排序中的合并算法，用两个游标指向两个单链表的位置，整体输入完毕后再做处理

此外由于Nk最大1000，因此也可以开至少1001个元素的vector，直接按秩映射

注意事项

如果相加后某一项为0，则需要将此项移除

输出时具体系数要保留一位小数

算法实现

#include <iostream>
#include <iomanip>
#include <map>

using namespace std;
int main(int argc, const char * argv[]) {
    map<int, double> result;
    int n, poly;
    double data;
    cin >> n;
    while (n--) {
        cin >> poly >> data;
        result[poly] += data;
    }
    cin >> n;
    while (n--) {
        cin >> poly >> data;
        result[poly] += data;
        if (result[poly] == 0) {
            result.erase(poly);
        }
    }
    cout << result.size();
    for (map<int, double>::reverse_iterator iter = result.rbegin(); iter != result.rend();
         iter++) {
        cout << " " << iter->first << " " << fixed << setprecision(1) << iter->second;
    }
    cout << endl;
    return 0;
}

结果

测试点	结果	用时(ms)	内存(kB)	得分/满分
0	答案正确	5	380	13/13
1	答案正确	6	384	2/2
2	答案正确	5	384	2/2
3	答案正确	6	372	2/2
4	答案正确	6	376	2/2
5	答案正确	8	384	2/2
6	答案正确	6	384	2/2