PAT甲级 1002. A+B for Polynomials（附测试点解释）

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

Input

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

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

题目大意为计算多项式的和（注意不要输出为0的项，计算项数时也不需要算上0的项）；

注意输出的格式 当项数为0是后面不需要加空格。

AC代码有两种：

1（一般思路）：

#include<bits/stdc++.h>
#include<string>
using namespace std;

int K1,K2;
int num,sum;
double key;
double mm[1001];
int main(void){
	cin>>K1;
	for(int i = 0;i < K1; ++i){
		cin>>num>>key;
		mm[num] += key;
	}
	cin>>K2;
	for(int i = 0;i < K2; ++i){
		cin>>num>>key;
		mm[num] += key;
	}
	for(int i = 0;i < 1001; i++)
		if(mm[i] != 0) sum++;
	cout<<sum;
	for(int i = 1000;i >= 0; i--)
		if(mm[i] != 0){
			cout<<" "<<i<<" ";
			cout<<setiosflags(ios::fixed)<<setprecision(1)<<mm[i];
//C++控制输出小数点位数与 printf("%.1lf",mm[i]); 作用相同。
		}
	return 0;
}

耗时及内存消耗1（一般方法耗时比较长）：

这里给出第二种方法（map）AC代码2：

#include<bits/stdc++.h>
#include<string>
#include<map>
using namespace std;

map<int,double> Map;
int cmp(pair<int,double> a,pair<int,double> b){
	return a.first > b.first;
}
int main(void)
{
	map<int,double>::iterator it;
	int K1,K2;
	cin>>K1;
	int key1,key2;
	double mm1,mm2;
	for(int i = 0;i < K1; ++i){
		cin>>key1>>mm1;
		if(Map[key1] == 0) Map[key1] = mm1;
		
		else if(Map[key1] != 0) 
			for(it = Map.begin(); it != Map.end(); it++)
				if(it -> first == key1)
					Map[key1] = it -> second + mm1;
	}//Map中key值相同的value相加
	cin>>K2;
	for(int i = 0;i < K2; ++i)
	{
		cin>>key2>>mm2;
		if(Map[key2] == 0) Map[key2] = mm2;
		else if(Map[key2] != 0)
			for(it = Map.begin(); it != Map.end(); it++)
				if(it -> first == key2)
					Map[key2] = it -> second + mm2;
	}
	vector<pair<int,double>> vec;
	for(it = Map.begin(); it != Map.end(); it++){
		vec.push_back(pair<int,double>(it->first,it->second));
	}	//Map不能直接排序，需要先pair到容器中，再排序
	sort(vec.begin(),vec.end(),cmp);
	int sum = 0;

	for(int i = 0;i < vec.size(); i++)
		if(vec[i].second != 0)
			sum++;
	cout<<sum;

	for(int i = 0;i < vec.size(); i++){
		if(vec[i].second != 0 && sum != 0){
			cout<<" "<<vec[i].first<<" ";
			printf("%.1lf",vec[i].second);	
		}
	}

	return 0;
}

耗时及内存消耗2：

 用Map和容器的耗时很短，并且对以后的做题有帮助。

代码思路仅供参考，如有不足和问题，请大佬提出。

最后

以上就是独特盼望为你收集整理的PAT甲级 1002. A+B for Polynomials（附测试点解释）的全部内容，希望文章能够帮你解决PAT甲级 1002. A+B for Polynomials（附测试点解释）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。