[数据结构与算法]1002. A+B for Polynomials(25分)

1002. A+B for Polynomials(25分)

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₁ a_N1 N₂ a_N2 … N_K a_NK

where K is the number of nonzero terms in the polynomial, N_i and aN_i (i=1,2,?,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤N_K<?<N₂<N₁≤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

结尾无空行

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct node
{
    int z;
    float x;
};

bool compare(node A, node B)
{
    return A.z > B.z;
}

int main()
{
    vector<node> A, B, C;
    node tmp;
    int a, b;
    cin >> a;
    for (int i = 0; i < a; i++)
    {
        cin >> tmp.z >> tmp.x;
        A.push_back(tmp);
    }
    cin >> b;
    for (int i = 0; i < b; i++)
    {
        cin >> tmp.z >> tmp.x;
        B.push_back(tmp);
    }
    // 排序
    sort(A.begin(), A.end(), compare);
    sort(B.begin(), B.end(), compare);
    // 双指针法
    int i, j;
    for (i = 0, j = 0; i < a && j < b;)
    {
        if (A[i].z > B[j].z)
        {
            tmp = A[i++];
            C.push_back(tmp);
        }
        else if (A[i].z < B[j].z)
        {
            tmp = B[j++];
            C.push_back(tmp);
        }
        else
        {
            tmp.z = A[i].z;
            tmp.x = A[i++].x + B[j++].x;
            // 系数为零就抵消了
            if (tmp.x)
            {
            C.push_back(tmp);
            }
            
        }
    }
    // 余值按序插入，2个while只有一个会被执行
    while (i < a)
    {
        tmp = A[i++];
        C.push_back(tmp);
    }
    while (j < b)
    {
        tmp = B[j++];
        C.push_back(tmp);
    }
    // 输出
    cout << C.size();
    for (node it : C)
    {
        printf(" %d %.1f", it.z, it.x);
    }
    system("pause");
    return 0;
}

受最近数据结构的影响，思维还没转变过来。想到的是传统的结构体解法，合并多项式借用了归并排序的思想，先将2个多项式降序排序，然后双指针法合并。卡壳的主要原因是没有考虑多项式相加为零要剔除的情况。

#include <iostream>
using namespace std;

int main()
{
    double N[1005] = {0};
    for (int i = 0; i < 2; i++)
    {
        int len;
        cin >> len;
        for (int k = 0; k < len; k++)
        {
            int z;
            double x;
            cin >> z >> x;
            N[z] += x;
        }
    }
    int count = 0;
    for (int i = 0; i <= 1000; i++)
    {
        if (N[i] != 0)
        {
            count++;
        }
    }
    cout << count;
    for (int i = 1000; i >= 0; i--)
    {
        if (N[i] != 0)
        {
            printf(" %d %.1f", i, N[i]);
        }
    }
    return 0;
}

数组下标表示指数，数组元素表示系数。简单明了。