【PAT】甲级1002 - A+B for Polynomials（多项式加法）
【PAT】甲级1002 - A+B for Polynomials（多项式加法）
题目链接：点击打开题目
1002.A+B for Polynomials (25)
时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B 判题程序 Standard 作者 CHEN, Yue 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
以前用链表来写，现在学会用vector，更方便了。
代码如下：
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<stack>
#include<vector>
using namespace std;
typedef long long LL;
#define CLR(a,b) memset(a,b,sizeof(a))
#define INF 0x3f3f3f3f
struct Node
{
double a;
int k;
bool friend operator < (Node a,Node b)
{
return a.k > b.k;
}
};
int main()
{
vector<Node> A;
vector<Node> B;
vector<Node> ans;
Node p;
int n,k;
double a;
cin >> n;
for (int i = 1 ; i <= n ; i++)
{
cin >> p.k >> p.a;
A.push_back(p);
}
cin >> n;
for (int i = 1 ; i <= n ; i++)
{
cin >> p.k >> p.a;
B.push_back(p);
}
sort(A.begin(),A.end());
sort(B.begin(),B.end());
//=================
// for (int i = 0 ; i < B.size() ; i++)
// cout << ' ' << B[i].k << ' ' << B[i].a;
// cout << endl;
//=================
int posA = 0;
int posB = 0;
while (posA != A.size() || posB != B.size())
{
if (posA == A.size())
{
p.k = B[posB].k;
p.a = B[posB].a;
if (p.a != 0)
ans.push_back(p);
posB++;
}
else if (posB == B.size())
{
p.k = A[posA].k;
p.a = A[posA].a;
if (p.a != 0)
ans.push_back(p);
posA++;
}
else if (A[posA].k == B[posB].k)
{
p.k = A[posA].k;
p.a = A[posA].a + B[posB].a;
if (p.a != 0)
ans.push_back(p);
posA++;
posB++;
}
else if (A[posA].k > B[posB].k)
{
p.k = A[posA].k;
p.a = A[posA].a;
if (p.a != 0)
ans.push_back(p);
posA++;
}
else //A[posA].k < B[posB].k
{
p.k = B[posB].k;
p.a = B[posB].a;
if (p.a != 0)
ans.push_back(p);
posB++;
}
}
cout << ans.size();
for (int i = 0 ; i < ans.size() ; i++)
printf (" %d %.1lf",ans[i].k,ans[i].a);
cout << endl;
return 0;
}腾讯云开发者
