PAT 1002 A+B for Polynomials
题目含义
就是两个指数多项式相加，然后输出结果。
结果第一个数是多项式中元素的个数，然后就是按照指数从大到小输出各个元素。
题解
这里需要注意的是第一个数的输出。联系常识，如果两个数相加为0，那么是不需要输出的，所以元素的个数有可能会比输入的要少。
还有就是注意输入的指数是从大到小的，也就是单看每一个输入都是有序的。这里的相加相当于广义上的两个有序序列合并起来。
网上题解很多，但是很少使用链表这种数据结构来解决，其实使用链表是比较合适的。把第一个序列固定，第二个遍历插入到第一个序列中即可。
这里为了方便，使用了STL中的list。这也是我第一次使用list，其实还是蛮好用的。
好的数据结构能省很多事。
代码
对于列表主要就是看如何插入和删除。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<map>
#include<set>
#include<list>
#include<sstream>
typedef long long ll;
using namespace std;
const double eps=1e-6;
const int inf=0x3f3f3f3f;
const int MAXN=1E1+7;
struct Node{
int n;
double a;
};
typedef list<Node> lnd;
lnd nodes;
int n, k;
int main()
{
cin>>k;
Node tmp;
for(int i=0; i<k; i++){
scanf("%d%lf", &tmp.n, &tmp.a);
nodes.push_back(tmp);
}
// for(lnd::iterator i = nodes.begin(); i!=nodes.end(); i++){
// cout<<(*i).n<<" "<<(*i).a<<endl;
// }
cin>>k;
lnd::iterator rs = nodes.begin();
for(int i=0; i<k; i++){
scanf("%d%lf", &tmp.n, &tmp.a);
for(;; rs++){
if(rs==nodes.end()){
nodes.insert(rs, tmp);
break;
}
if((*rs).n==tmp.n){
(*rs).a += tmp.a;
if((*rs).a==0.0)
rs = nodes.erase(rs); //返回当前删除元素的下一个位置
break;
}
else if((*rs).n < tmp.n){
lnd::iterator j = nodes.insert(rs, tmp); //insert函数是有返回值的，返回新插入的位置，就是rs的上一个位置。
// printf("%d *** %d\n", (*rs).n, (*j).n);
break;
}
}
}
n = nodes.size();
cout<<n;
lnd::iterator i = nodes.begin();
while(i!=nodes.end()){
printf(" %d %.1f", (*i).n, (*i).a);
i++;
}
printf("\n");
return 0;
}