PAT Advanced 1002. A+B for Polyn

我的PAT系列文章更新重心已移至Github，欢迎来看PAT题解的小伙伴请到Github Pages浏览最新内容。此处文章目前已更新至与Github Pages同步。欢迎star我的repo。

题目

This time, you are supposed to find where and 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:

...

where is the number of nonzero terms in the polynomial, and
( ) are the exponents and coefficients,
respectively. It is given that ， .

Output Specification:

For each test case you should output the sum of and 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

思路

最初由于数学概念的理解错误，纠结了半天。0是零多项式，在题中将之归于“0项”多项式。当然了，实际是没有0项多项式的，只有零多项式，但是非要输出个结果，0还是合理的。我一开始把0当成只有常数项的一项多项式，结果最后一测试点老过不去。。。。

很多人都用1000长度的数组存储多项式，确实思路简单，且并不是很浪费空间。我用了另一种思路，用数组模仿链表的实现。将A、B两多项式由次数从高到低依次计算，存入新数组。

疑问：最初最后一个测试点没过的时候，我以为又是小负数近似格式的问题（见PAT Basic 1051. 复数乘法 (15)（C语言实现）），便将系数绝对值小于0.05的项全忽略了。当然这么做也通过了，可能输入保证了精度也只有1位小数，这样就没有这个必要了。

代码

最新代码@github，欢迎交流

#include <stdio.h>
#include <math.h>

typedef struct Poly{
    double coef;
    int exp;
} Poly[20];

int main()
{
    int KA, KB, Ksum = 0;
    Poly A, B, sum;

    scanf("%d", &KA);
    for(int i = 0; i < KA; i++)
        scanf("%d %lf", &A[i].exp, &A[i].coef);

    scanf("%d", &KB);
    for(int i = 0; i < KB; i++)
        scanf("%d %lf", &B[i].exp, &B[i].coef);

    int i = 0, j = 0;
    while(i < KA || j < KB)
    {
        if(i == KA || (j < KB && A[i].exp < B[j].exp))
        {
            sum[Ksum].exp = B[j].exp;
            sum[Ksum].coef = B[j++].coef;
        }
        else if(j == KB || (i < KA && A[i].exp > B[j].exp))
        {
            sum[Ksum].exp = A[i].exp;
            sum[Ksum].coef = A[i++].coef;
        }
        else
        {
            sum[Ksum].exp = A[i].exp;
            sum[Ksum].coef = A[i++].coef + B[j++].coef;
        }
        if(fabs(sum[Ksum].coef) >= 0.05) Ksum++;
    }

    printf("%d", Ksum);

    for(int i = 0; i < Ksum; i++)
        printf(" %d %.1lf", sum[i].exp, sum[i].coef);

    return 0;
}