苏州OJ c001: 合并同类项

た入场券 2022-08-10 10:58 146阅读 0赞

**内容：**

【问题描述】  
给出两个多项式y1和y2，请你合并同类项。  
【输入】  
输入数据共两行，每行代表一个多项式。每个多项式按如下形式给出：  
a1 b1 a2 b2 … ai bi … an bn  
其中a1~an均为整数，表示此多项式n项的系数，b1~bn均为整数，表示此多项式n项的指数。数字与数字之间用一个空格隔开，最后一个数字之后没有空格。  
【输出】  
输出数据仅一行，表示合并后的多项式，格式同输入形式，按指数递减排列。  
【样例】  
输入

3 7 5 6 -4 5 -3 2 -8 1 -2 0  
9 12 -6 8 -5 7 -5 6 1 4 -8 3 6 2 7 1 3 0

输出

9 12 -6 8 -2 7 -4 5 1 4 -8 3 3 2 -1 1 1 0

/*
     * 这个题目有三个陷阱
     * 1.在同一行中可能出现指数相同的两个系数
     * 2.如果合并后系数为0则不输出
     * 3.如果合并后所有系数为0则输出0
     */
    #include <iostream>
    #include <map>
    #include <functional>
    #include <stdio.h>
    using namespace std;
    
    int main()
    {
    	// key-指数 value-系数 添加进两个map
    	int xs, zs;
    	map <int, int, greater<int> > iMap1, iMap2;
    	while (cin >> xs >> zs) {
    		char c = getchar();
    		iMap1[zs] += xs;
    		if (c == '\n') break;
    	}
    	while (cin >> xs >> zs) {
    		iMap2[zs] += xs;
    	}
    	// 合并到iMap1
    	map<int, int>::iterator iter = iMap2.begin();
    	while (iter != iMap2.end()) {
    		iMap1[iter->first] += iMap2[iter->first];
    		++iter;
    	}
    	// 去除系数为0的
    	iter = iMap1.begin();
    	map<int, int>::iterator tmp;
    	while (iter != iMap1.end()) {
    		tmp = iter;
    		++iter;
    		if (tmp->second == 0) {
    			iMap1.erase(tmp);
    		}
    	}
    	// 输出
    	iter = iMap1.begin();
    	if (iter == iMap1.end())
    		cout << "0";
    	else {
    		while (iter != iMap1.end()) {
    			cout << iter->second << " " << iter->first;
    			if (++iter != iMap1.end()) {
    				cout << " ";
    			}
    		}
    	}
    	return 0;
    }