PAT A1002 A+B for Polynomials(25)[多项式A+B, 高精度]

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 \quad N_1 a_{N_1} a_{N_2} … 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 \leq K \leq 0，0 \leq N_K \cdots \leq N_2 \leq N_1 \leq 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

思路1

1. 使用一个数组存储对应指数的系数
2. 将对应指数相同的项(下标相同的项)相加
3. 注意系数为 double

代码1

#include <iostream>
using namespace std;
const int N = 1010;
double a[N];
int main()
{
    int k, ex;
    double co;  // 系数 
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%lf", &ex, &co);   
        a[ex] = co; 
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%lf", &ex, &co);   
        a[ex] += co;        
    }
    int cnt = 0;
    for(int i = 0; i < N; i++)
        if(a[i])
            cnt++;
    printf("%d", cnt);
    for(int i = N - 1; i >= 0; i--)
    {
        if(a[i])
            printf(" %d %.1f", i, a[i]);
    }
    puts("");
    return 0;
}

思路2

1. 使用一个 map 存储，会计数并且排序

代码2

#include <bits/stdc++.h>
using namespace std;
map<int, double> mp;
int main()
{
    int k, a;
    double b;
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%lf", &a, &b);
        mp[a] = b;
    }
    scanf("%d", &k);
    for(int i = 0; i < k; i++)
    {
        scanf("%d%lf", &a, &b);
        mp[a] += b;
    }
    printf("%d", mp.size());
    for(auto it = mp.rbegin(); it != mp.rend(); it++)
        printf(" %d %.1f", it->first, it->second);
    puts("");
    return 0;
}