PAT 1002 A+B for Polynomials (25分)

题目链接：点击这里

题意：给定两个多项式 $A$ 和 $B$，计算 $A+B$ 的结果。

思路：多项式相加也就是合并同类项，如下表所示，可以用一维数组存储多项式。

样例 2 1 2.4 0 3.2 可以表示成 $2.4x+3.2$，其在数组中的存储如下：

样例 2 2 1.5 1 0.5 可以表示成 $1.5x^2+0.5x$，其在数组中的存储如下：

两者相加的结果为 $1.5x^2+2.9x+3.2$，其在数组中的存储如下：

时间复杂度为 $O(n)$

AC代码：

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1010; double a[N], b[N], c[N]; int main() { int n, exp, maxe = -1; double coe; scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d%lf", &exp, &coe); maxe = max(maxe, exp); a[exp] += coe; } scanf("%d", &n); for(int i = 0; i < n; i++) { scanf("%d%lf", &exp, &coe); maxe = max(maxe, exp); b[exp] += coe; } for(int i = 0; i <= maxe; i++) c[i] = a[i] + b[i]; int ans = 0; for(int i = maxe; i >= 0; i--) ans += c[i] != 0; printf("%d", ans); for(int i = maxe; i >= 0; i--) { if(c[i] != 0) printf(" %d %.1f", i, c[i]); } return 0; }

微信公众号《算法竞赛求职》，致力于详细讲解竞赛和求职所涉及到的算法原理和模板。欢迎关注，一起交流进步！