【PAT甲级】A+B for Polynomials

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

本文链接：https://blog.csdn.net/weixin_42449444/article/details/88827937

Problem Description：

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

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.

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.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 2 1.5 1 2.9 0 3.2

解题思路：

直接无脑map啊。我一开始只创建了一个根据key值降序排列的map（key是多项式的指数、value是多项式的系数），然后无脑将指数相同的项进行相加，最后输出map.size() 再无脑for-each进行输出（需要注意的是结果保留1位小数）。然而！提交之后有测试用例WA啦。原来，输入的某些项系数相加之后可能为0，此时项数要减1。于是我又创建了一个根据key值降序排列的map（取名为ans，用来存放系数相加后不为0的项），最后无脑for-each输出就AC啦。

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
    map<int,double,greater<int>> m;   //map的key是指数,value是系数,根据key来降序排列
    for(int i = 0; i < 2; i++)
    {
        int K;
        cin >> K;
        while(K--)
        {
            int t1;
            double t2;
            cin >> t1 >> t2;
            m[t1] += t2;
        }
    }
    //需要注意,输入的某些项相加后可能为0,此时项数减1,并且不对该项进行输出
    map<int,double,greater<int>> ans;
    for(auto it : m)
    {
        if(it.second != 0)
        {
            ans[it.first] = it.second;
        }
    }
    cout << ans.size();
    for(auto it : ans)
    {
        cout << " " << it.first;
        cout << " " << setiosflags(ios::fixed) << setprecision(1) << it.second;  //保留一位小数
    }
    return 0;
}