PAT1002

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

这一次，你被要求计算A+B当A和B是两个多项式的时候。

Input

Each input file contains one test case. Each case occupies 2 lines, and each line contains the information of a polynomial:

对于每一个输入文件包含一个测试用例，每个测试用例包含两行，每一行包含多项式的信息如下。

K N1 a_N1 N2 a_N2 ... NK a_NK, where K is the number of nonzero terms in the polynomial,

Ni and a_Ni (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

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

总结一下有几点，第一点题目意思需要读懂的同时注意题目的一些细节，比如需要保留小数。

这道题目在想的时候，其实需要一点考虑的是数据结构。

用什么样的数据结构去存会比较合理。

下面是我的思考过程，一开始我就想到的时候就觉得数组是最快的，存放固定的常数位置对应的指数，然后对应的相加。

看一下数据大小，1000，那么开1000大小的数组，然后最多数据是10+10个。也就是说，数组中会有很大一部分的空余。

确实很浪费空间。然后我在想不浪费的话就是线性表了，也就是链表，链表插入是没有问题的，主要的问题是查询，查询到相应的位置，然后加数据，或者插入数据，这样的话因为最多是20个数据，就算不用二分查询，最坏复杂度也能在N！

也就是（1+20）*20/2=210左右，比1000的数组循环一边要快。

这是对于数据结构的想法，但是具体的题目来说，做题讲究一些代码的复杂程度，用数组实现比较方便，所以我依旧选择使用数组完成。

下面是能过的代码。

#include<cstdio>

#include<cstdlib>

#include<iostream>

#include<algorithm>

#include<string.h>

using namespace std;

float maps[];

int main()

{

    int n,x;

    float y;

    int aN=;

    cin>>n;

    while (n--)

    {

        cin>>x>>y;

        maps[x] = y;

        aN++;

    }

    cin>>n;

    while (n--)

    {

        cin>>x>>y;

        if(maps[x] == )

            aN++;

        maps[x] += y;

        if(maps[x] == )

            aN--;

    }

    if(aN == )

    {

        cout<<aN;

        return ;

    }

    else

    {

        cout<<aN<<" ";

    }

    for (int i = ; i >= ; i--)

    {

        if(aN ==  && maps[i] != )

        {

            printf("%d %.1f",i,maps[i]);

            break;

        }

        else if(maps[i] != )

        {

            printf("%d %.1f ",i,maps[i]);

            aN--;

        }

    }

    return ;

}

然后提一些需要改进的地方。

输出的时候可以使用前缀空格输出。前面直接输出一个相数aN就行了，不用加空格。

printf(" %d %.1f",i,maps[i]);

这样可以减少判断最后输出格式的问题。

其中还要注意的是，多项式加法之后会出现0

所以会出现相数减少的情况，如果合并了，那么相数需要减少，这里我也错过，导致WA。

巴特西

PAT1002

最新文章

热门文章