PAT-ADVANCED1002——A+B for Polynomials

我的PAT-ADVANCED代码仓：https://github.com/617076674/PAT-ADVANCED

原题链接：https://pintia.cn/problem-sets/994805342720868352/problems/994805526272000000

题目描述：

题目翻译：

1002 多项式形式的A + B

当A和B都是多项式时，你需要计算A + B。

输入格式：

每个输入文件包含一个测试用例。每个测试用例占2行，每行包含一个多项式的信息：

K N​1​​ a​N​1​​​​ N​2​​ a​N​2​​​​ ... N​K​​ a​N​K​​​​

其中K是多项式中非零项的个数，Ni和aNi(i = 1, 2, ..., K)分别是指数和系数。1 <= K <= 10，0 <= NK < ... < N2 < N1 <= 1000。

输出格式：

对每个测试用例，你需要在一行中输出A + B的结果，其形式和输入相同。行末不得有多余空格，系数精确到小数点后1位。

输入样例：

2 1 2.4 0 3.2
2 2 1.5 1 0.5

输出样例：

3 2 1.5 1 2.9 0 3.2

知识点：哈希表

思路：开一个大小为1001的数组记录系数

时间复杂度是O(K1 + K2)，其中K1是第一个输入多项式的非零项个数，K2是第二个输入多项式的非零项个数。空间复杂度是O(1001)。

C++代码：

#include<iostream>
#include<vector>
#include<utility>
#include<cmath>

using namespace std;

int main(){
	double coefficients[1001];	//coefficients[i]代表该项系数为coefficients[i]，指数为i
	fill(coefficients, coefficients + 1001, 0.0);
	int K, N;
	double aN;
	scanf("%d", &K);
	for(int i = 0; i < K; i++){
		scanf("%d %lf", &N, &aN);
		coefficients[N] += aN;
	}
	scanf("%d", &K);
	for(int i = 0; i < K; i++){
		scanf("%d %lf", &N, &aN);
		coefficients[N] += aN;
	}
	vector<pair<int, double> > results;
	for(int i = 1000; i >= 0; i--){
		if(fabs(coefficients[i]) >= 0.00000001){
			results.push_back(make_pair(i, coefficients[i]));
		}
	}
	printf("%d", results.size());
	for(int i = 0; i < results.size(); i++){
		printf(" %d %.1f", results[i].first, results[i].second);
	}
	return 0; 
}

C++解题报告：