PATEST-A1002-题解

题目

多项式加法。

想法

本以为要用数组来解，但是想一想光搜索就容易爆时间，我又不想自己写一个二叉排序树的算法。

这样一想，没有思路，我就去看题解了。

发现 map 正好是一个映射关系，恰好符合这道题的要求。

所以本题的解题思路就是，如果 first 对应的值存在就加上 second，对应的值不存在就存入，之后利用反向迭代器统计非零元个数，并输出结果。

最后输出应当使用 printf ，使用 cout 会爆流。

代码

#include <iostream>
#include <map>

using namespace std;

int main()
{
	int a_count, b_count;		 //多项式非零元个数
	map<int, double> p;
	
	
	cin >> a_count;
	for (int j = 0; j < a_count; ++j)
	{
		int exp;//指数
		double coe;//真数
		cin >> exp >> coe;
		/*map.insert()函数在执行时,若const值已经存在,就不再执行插入操作*/
		if (!p.insert(make_pair(exp, coe)).second )
		{
			p[exp] = p[exp] + coe;
		}

	}
	
	
	cin >> b_count;
	for (int j = 0; j < b_count; ++j)
	{
		int exp;//指数
		double coe;//真数
		cin >> exp >> coe;
		if (!p.insert(make_pair(exp, coe)).second )
		{
			p[exp] = p[exp] + coe;
		}

	}
	
	
	int total_count = 0;
	for (map<int, double>::reverse_iterator iter = p.rbegin();
		iter != p.rend(); iter++)
	{
		if ((*iter).second != 0)
		{
			total_count++;
		}
	}
	
	
	cout << total_count;
	for (map<int, double>::reverse_iterator iter = p.rbegin(); 
		iter != p.rend(); iter++)
	{
		if ((*iter).second != 0)
		{
			printf(" %d %.1lf", (*iter).first, (*iter).second);
		}
	}


}