1002 A+B for Polynomials (25 分)

1. 题目

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 N1 aN1 N2 aN2 ... NK aNK

where K is the number of nonzero terms in the polynomial, Ni and aNi (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10，0≤NK<⋯<N2<N1≤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

2. 题意

多项式求和，将指数相同的项进行系数求和，其余项正常输出！

3. 思路——简单模拟

注意：当两项指数相同时，系数会相加，如果系数相加为0，那么这一项不应该被输出！（这个很坑，一开始没想到，测试点只能过两三个）

具体思路：

刚好多项式的一项是一个指数值（int ）和一个系数值（double）组成，使用pair进行存储。
第一个多项式A读入一个pair数组中，在第二个多项式B读入过程中，每一项与第一个多项式A进行对比：
1. 如果对应项指数相同，则系数相加，系数相加不为0，则加入结果中。
2. 如果指数较大项加入到结果中：
  1. 如果B项指数大于A项，则将B项加入结果
  2. 如果A项指数大于B项，则将A项加入结果；并移动指针，比较A项下一项的指数是否大于B项当前项，如果大于则继续加入结果；以此类推，直到A项指数不再大于B项。

4. 代码

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, double> PID;

// 这题有一个坑，就是如果系数相加为0，那么这一项就不要输出了！！！！！！ 

int main()
{
	int k1;
	cin >> k1;
	PID A[k1];	// 多项式A
	for (int i = 0; i < k1; ++i)
		cin >> A[i].first >> A[i].second;
  	
        // 多项式A和多项式B相加结果
	vector<PID> res;
	int x;
	double y;
	int j = 0;
	int k2;
	cin >> k2;
	for (int i = 0; i < k2; ++i)
	{
		PID B;
                // 输入多项式B的第i项
		cin >> B.first >> B.second;
                // 比较两个多项式指数前，需要判断指向多项式A的下标是否已经超过该多项式
		if (j < k1)	
		{            
			if (B.first > A[j].first);	// 如果B项指数大于A项，则不需要做什么额外操作
			else if (B.first == A[j].first)	// 如果B项指数等于B项，则系数需要相加
			{
				B.second += A[j++].second;
			} else    // 如果B项指数小于A项
			{
                                // 则将小于A项大于B项的所有项加入结果集
				while (j < k1 && A[j].first > B.first) 
				{
					res.push_back(A[j++]);
				}
                                // 如果A项等于B项，还需做系数相加操作
				if (j < k1 && A[j].first == B.first)
				{
					B.second += A[j++].second;
				}
			}	
		}
		// 上面操作完成后，都要进行将B项加入结果集的操作，但需要判断系数不为0，为0则不需要加入结果集
		if (B.second != 0) res.push_back(B);
	}
        // 如果B项都添加完成后，还有A的多项式，则依次加入结果集
	while (j < k1)
	{
		res.push_back(A[j++]);
	}
	cout << res.size();
	for (int i = 0; i < res.size(); ++i)
	{
		cout << " " << res[i].first;
		printf(" %.1lf", res[i].second);
	}
	cout << endl;
	return 0;
}