PAT-A-1002

所有甲级题全解

原题链接

生僻词汇

Polynomial 多项式

exponent 指数

coefficient 系数

题意

给 A，B 两个多项式，求和

知识点

变量类型合理选择

简单在线处理

数组下标模拟多项式指数

格式化输出

思路

$N$ 上界只有 $10^3$，400ms 时限，两个数组直接暴力检索显然可以接受，但是在线处理可以保证时间复杂度始终在 $O(n)$

代码

#include <cstdio>

const int maxN = 1005;
double arr[maxN] = {0};
int k, n, cnt = 0;
double an;

int main() {
    int t = 2;
    
    //循环2次，输入2个多项式
    while (t--) {
        scanf("%d", &k);

        //在线处理
        while (k--) {
            scanf("%d%lf", &n, &an);
            arr[n] += an;
        }
    }

    //非零项数
    for (int i = 0; i < maxN; i++) {
        if (arr[i] != 0) cnt++;
    }

    //输出
    printf("%d", cnt);
    for (int i = maxN - 1; i >= 0; i--) {
        if (arr[i] != 0) {
            printf(" %d %.1f", i, arr[i]);
        }
    }
}