(PAT 1002) A+B for Polynomials(利用双指针和归并排序思想)

短命女 2022-03-26 15:53 123阅读 0赞

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

解题思路:

模拟二项式相加,输入第一个数表示有几个非零项(输入的都是非零项)

然后输入的第一个为幂次数,第二个为系数

来看这么个例子:

4 4 0.5 2 5.6 1 -2.7 0 3.6

3 3 -2.1 2 -5.6 1 2.7

我们把幂次从小到大排序,然后设置两个指针,分别指向两列数中第一个元素的幂次和系数

然后模仿归并排序中的思想,如果所指元素幂次相等,则把系数相加后放到一个新的二次项中

如果第一个元素大于第二个,则移动第一个指针,否则移动第二个指针

直到所有的元素都相加为止

### 如果相加系数为0,那么就不放入到新二次项中 ###

注意:

double型数据读入时要用 %lf 保留几位小数输出时用%.xf

#include<iostream>
    #include<algorithm>
    using namespace std;
    struct Greed {
    	int mi;
    	double term;
    }FirstGreeds[10010],secondGreeds[10010],finalGreeds[10010];
    
    bool cmp(Greed A, Greed B) {
    	return A.mi > B.mi;
    }
    
    int main() {
    	int N, M;
    	scanf("%d", &N);
    	for (int i = 0; i < N; ++i) {
    		int mi;
    		double term;
    		scanf("%d %lf", &mi, &term);
    		FirstGreeds[i].mi = mi;
    		FirstGreeds[i].term = term;
    	}
    
    
    	scanf("%d", &M);
    	for (int i = 0; i < M; ++i) {
    		int mi;
    		double term;
    		scanf("%d %lf", &mi, &term);
    		secondGreeds[i].mi = mi;
    		secondGreeds[i].term = term;
    	}
    	sort(FirstGreeds, FirstGreeds + N, cmp);
    	sort(secondGreeds, secondGreeds + M, cmp);
    	int point1 = 0, point2 = 0;
    	int index = 0;
    	int countss = 0;
    	while (point1 < N && point2 < M) {
    		if (FirstGreeds[point1].mi == secondGreeds[point2].mi) {
    			double newTerm = FirstGreeds[point1].term + secondGreeds[point2].term;
    			if (newTerm == 0) {
    				point1++, point2++;
    				continue;
    			}
    			else {
    				finalGreeds[index].mi = FirstGreeds[point1].mi;
    				finalGreeds[index++].term = newTerm;
    				point1++, point2++;
    				countss++;
    			}
    		}
    		else if (FirstGreeds[point1].mi > secondGreeds[point2].mi) {
    			finalGreeds[index].mi = FirstGreeds[point1].mi;
    			finalGreeds[index++].term = FirstGreeds[point1].term;
    			point1++;
    			countss++;
    		}
    		else {
    			finalGreeds[index].mi = secondGreeds[point2].mi;
    			finalGreeds[index++].term = secondGreeds[point2].term;
    			point2++;
    			countss++;
    		}
    	}
    	while (point1 < N) {
    		finalGreeds[index].mi = FirstGreeds[point1].mi;
    		finalGreeds[index++].term = FirstGreeds[point1].term;
    		point1++;
    		countss++;
    	}
    	while (point2 < M) {
    		finalGreeds[index].mi = secondGreeds[point2].mi;
    		finalGreeds[index++].term = secondGreeds[point2].term;
    		point2++;
    		countss++;
    	}
    
    	cout << countss;
    	for (int i = 0; i < index; ++i) {
    		printf(" %d %.1f", finalGreeds[i].mi, finalGreeds[i].term);
    	}
    
    	
    	system("PAUSE");
    	return 0;
    }