题目

题意简单，两个多项式相乘。

每一个多项式K是项数，接着是K个指数，常数。

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 N​1​​ a​N​1​​​​ N​2​​ a​N​2​​​​ ... N​K​​ a​N​K​​​​

where K is the number of nonzero terms in the polynomial, N​i​​ and a​N​i​​​​ (i=1,2,⋯,K) are the exponents and coefficients, respectively. It is given that 1≤K≤10, 0≤N​K​​<⋯<N​2​​<N​1​​≤1000.

Output Specification:

For each test case you should output the product 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 up to 1 decimal place.

Sample Input:

2 1 2.4 0 3.2
2 2 1.5 1 0.5

Sample Output:

3 3 3.6 2 6.0 1 1.6

分析

记录一下 聪明反被聪明误的zz

开始以为题目没有说指数和常数的范围，于是都开了double 。既然都是double ,那就不能用数组了，就得用map<double , double>了。

接着正常的循环相乘，相加操作。

输出的时候，map是已经给排序好了的啊，map<key , value> 那肯定是按key排序好了的啊。一输出，发现，不对。

跟标答正好返了过来。

没问题，我们有map的逆序输出操作 ：可以使用反向迭代器reverse_iterator反向遍历map容器中的数据，它需要rbegin()和rend()方法指出反向遍历的起始位置和终止位置。 

map<int , double > ::reverse_iterator ansit;
for(ansit = ans.rbegin() ; ansit != ans.rend() ; ansit ++)

接下来，发现测试点0错了。

测试点0的错误是因为，如果常数是0 ， 这一项就不用输出了，结果的项数也应该不算在内！

依稀记得自己以前也这样错过。。。。。

代码

#include<iostream>
#include<algorithm>
#include<sstream>
#include<string.h>
#include<map>
using namespace std;
//多项式相乘
map<int , double > pa;
map<int , double > pb;
map<int , double > ans;

int main()
{

    int k1;
    cin >> k1;
    for(int i = 0 ; i < k1 ; i++)
    {
        int exp  ;
        double  coef;
        cin >> exp >> coef;
        pa[exp] = coef;
    }
    int k2;
    cin >> k2;
    for(int i = 0 ; i < k2 ; i++)
    {
        int exp  ;
        double  coef;
        cin >> exp >> coef;
        pb[exp] = coef;
    }

    map<int , double >::iterator pait , pbit ;
    map<int , double > ::reverse_iterator ansit;
    for(pait = pa.begin() ; pait!=pa.end() ; pait++)
    {
        int  paexp = pait->first;
        double pacoef = pait->second;
        //cout << pacoef << " " <<  paexp << endl;
        for(pbit = pb.begin() ; pbit != pb.end() ;pbit++)
        {
            int pbexp = pbit->first;
            double pbcoef = pbit ->second;

            int ansexp = paexp + pbexp;
            double anscoef = pbcoef * pacoef;
            ans[ansexp] += anscoef;

        }
    }

    int cnt = 0;
    for(ansit = ans.rbegin() ; ansit != ans.rend() ; ansit ++)
    {
        if(ansit->second == 0) continue;
            cnt ++;
    }
    cout << cnt;

    for(ansit = ans.rbegin() ; ansit != ans.rend() ; ansit ++)
    {
        if(ansit->second == 0) continue;
        printf(" %d %.1f" , ansit->first , ansit->second);

    }
}