[PAT Advanced Level]1002. A+B for Polynomials (25)

思路：先将两个多项式存入到两个数组中，再利用归并排序的方法合并两个多项式。

注意：遇到相加后系数为0的项要舍弃，项的数目也不能+1。

改进：写到一半发现项的指数给定了范围[0...1000]，那么可以使用间址技巧，将项的指数看成数组的下标，这样扫描一遍就可以得到结果。

#include <iostream>  
#include <fstream>  
#include <vector>  
#include <iomanip>  
using namespace std;  
  
  
struct item  
{  
    item(){}  
    item(int e, double c)  
    {  
        this->exp = e;  
        this->coef = c;  
    }  
    int exp;  
    double coef;  
};  
void merge(item *items1, item *items2, int a, int b);  
int main()  
{  
    //fstream cin("a.txt");  
  
    int a,b;  
    cin>>a;  
    int tmp = a;  
    item *items1 = new item[a];  
    while (tmp--)  
    {  
        int exp;  
        double coef;  
        cin>>exp>>coef;  
        item it(exp, coef);  
        items1[a - tmp - 1] = it;  
    }  
    cin>>b;  
    tmp = b;  
    item *items2 = new item[b];  
    while (tmp--)  
    {  
        int exp;  
        double coef;  
        cin>>exp>>coef;  
        item it(exp, coef);  
        items2[b - tmp - 1] = it;  
    }  
  
    merge(items1, items2, a, b);  
    return 0;  
}  
  
void merge(item *items1, item *items2, int a, int b)  
{  
    vector<item> v;  
    int i = 0,j = 0;  
    for(;i < a && j < b;)  
    {  
        if(items1[i].exp > items2[j].exp)  
        {  
            if(items1[i].coef != 0)  
                v.push_back(items1[i]);  
            i++;  
        }  
        else if(items1[i].exp < items2[j].exp)  
        {  
            if(items2[j].coef != 0)  
                v.push_back(items2[j]);  
            j++;  
        }  
        else  
        {  
            item it(items1[i].exp, items1[i].coef + items2[j].coef);  
            if (it.coef != 0)  
                v.push_back(it);  
            i++;  
            j++;  
        }  
    }  
  
    if(i == a)  
    {  
        while (j < b)  
        {  
            if(items2[j].coef != 0)  
                v.push_back(items2[j]);  
            j++;  
        }  
    }  
    else  
    {  
        while (i < a)  
        {  
            if(items1[i].coef != 0)  
                v.push_back(items1[i]);  
            i++;  
        }  
    }  
  
    cout<<v.size();  
    for (int i = 0; i < v.size(); i++)  
    {  
        cout<<" "<<v[i].exp<<" "<<fixed<<setprecision(1)<<v[i].coef;  
    }  
    cout<<endl;  
}

补充：软件开发 , C++ ,