学步园

本来以为这道题挺简单的，结果一做才发现漏洞百出，学习了map 的使用，加深了stl中容器的学习和相关算法的应用

unique函数可以抽机会再用一用，实际上这些stl里面的算法可以通过自己写基础代码实现，就是指针加单纯数组加N多变量，但是太繁琐和费时间，既然已经提供了成型的算法为何不学习和应用呢？虽然这些成型的算法不太有助于对基础性知识的理解，但是你有个大概印象就可以了。

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
/* map的使用，sort 仅用于vector里面，倒序迭代器
一开始就应该结构体对象，结果还在用单纯的数组做了半天

*/
using namespace std;
//从数组转换成结构体数组
typedef struct node
{
	int coef ;
	int power;
}; // 这里声明 对象的时候还需要确认

bool comp(const node &valA,const node &valB)
{
	return (valA).power > (valB).power;
}

int main()
{
	int n,m;
	cin>> n;
	map<int,int> addMap;
	node *dataA = new node[n];
	if(n == 0)
		dataA[0].coef = dataA[0].power = 0;
	for(int i = 0;i < n;i++)
	{
		cin >> dataA[i].coef;
		cin >> dataA[i].power;
		addMap[dataA[i].power] = dataA[i].coef;//以power为键，系数为值
	}
	cin>> m;
	node *dataB = new node[m];
	if(m == 0)
		dataB[0].coef = dataB[0].power = 0;
	for(int i = 0;i < m;i++)
	{
		cin >> dataB[i].coef;
		cin >> dataB[i].power;
		if(addMap.count(dataB[i].power))//存在对应的键，加上去
			addMap[dataB[i].power] += dataB[i].coef; //map 的构建默认是按照键值的增序排序的，而不是按照你放入的先后顺序
		else
			addMap[dataB[i].power] = dataB[i].coef;
	}
	

	//乘积
	node *mulResult = new node[n*m];
	int mulLength = 0;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m; j++)
		{
			mulResult[mulLength].coef = dataA[i].coef * dataB[j].coef;
			mulResult[mulLength].power = dataA[i].power + dataB[j].power;
			mulLength++;
		}
	}
	
	if(mulLength > 0)
	{
		sort(mulResult,mulResult + mulLength,comp);
		vector<node> mulResultSort(mulResult,mulResult + mulLength);
		// 可以用unique函数来实现，去掉重复的元素，返回最后一个元素迭代器
		vector<node>::iterator iter,titer;
		iter = mulResultSort.begin();
		while( iter< mulResultSort.end())
		{
			titer = iter;
			iter++;
			while( iter< mulResultSort.end()&&(*titer).power == (*iter).power)
			{
				(*titer).coef += (*iter).coef;
				(*iter).power = -1;
				iter ++;//			
			}
		}


		bool flag = false;
		for(iter = mulResultSort.begin();iter < mulResultSort.end();iter++)
		{
			if((*iter).power == -1 || (*iter).coef == 0)
				continue;
			
			if(flag)
				cout<<" ";
			
			cout<<(*iter).coef<<" "<<(*iter).power;
			flag = true;
		}
	}
	else
		cout<<"0 0";
	cout<<endl;
	//和的输出
	//倒序只要这样就可以了么。。。还要去用sort只适用于vector
	map<int,int>::reverse_iterator miter = addMap.rbegin();
		bool tag = false;
		for(;miter != addMap.rend();++miter)
		{
			if(miter->second == 0)
				continue;
			if(tag)
				cout<<" ";
			cout<<miter->second<<" "<<miter->first;
			tag = true;
			
		}
		if(!tag)
			cout<<"0 0";
		return 0;
}