1002. A+B for Polynomials(25分)
This time, you are supposed to find A+B where A and B are two polynomials.
Input Specification:
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 Specification:
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 结尾无空行
#include <iostream> #include <vector> #include <algorithm> using namespace std; struct node { int z; float x; }; bool compare(node A, node B) { return A.z > B.z; } int main() { vector<node> A, B, C; node tmp; int a, b; cin >> a; for (int i = 0; i < a; i++) { cin >> tmp.z >> tmp.x; A.push_back(tmp); } cin >> b; for (int i = 0; i < b; i++) { cin >> tmp.z >> tmp.x; B.push_back(tmp); } // 排序 sort(A.begin(), A.end(), compare); sort(B.begin(), B.end(), compare); // 双指针法 int i, j; for (i = 0, j = 0; i < a && j < b;) { if (A[i].z > B[j].z) { tmp = A[i++]; C.push_back(tmp); } else if (A[i].z < B[j].z) { tmp = B[j++]; C.push_back(tmp); } else { tmp.z = A[i].z; tmp.x = A[i++].x + B[j++].x; // 系数为零就抵消了 if (tmp.x) { C.push_back(tmp); } } } // 余值按序插入，2个while只有一个会被执行 while (i < a) { tmp = A[i++]; C.push_back(tmp); } while (j < b) { tmp = B[j++]; C.push_back(tmp); } // 输出 cout << C.size(); for (node it : C) { printf(" %d %.1f", it.z, it.x); } system("pause"); return 0; }
受最近数据结构的影响，思维还没转变过来。想到的是传统的结构体解法，合并多项式借用了归并排序的思想，先将2个多项式降序排序，然后双指针法合并。卡壳的主要原因是没有考虑多项式相加为零要剔除的情况。
#include <iostream> using namespace std; int main() { double N[1005] = {0}; for (int i = 0; i < 2; i++) { int len; cin >> len; for (int k = 0; k < len; k++) { int z; double x; cin >> z >> x; N[z] += x; } } int count = 0; for (int i = 0; i <= 1000; i++) { if (N[i] != 0) { count++; } } cout << count; for (int i = 1000; i >= 0; i--) { if (N[i] != 0) { printf(" %d %.1f", i, N[i]); } } return 0; }
数组下标表示指数，数组元素表示系数。简单明了。
