PTA 1002 A+B for Polynomials
2020-04-24 16:00:31来源:博客园 阅读 ()
PTA 1002 A+B for Polynomials
题目翻译
现在,你需要求出A,B两个多项式的相加结果。
输入要求
每一个输入文件包含一个测试样例。每一个样例占两行并且每行包含多项式的信息:
\(K\space N_1 \space a_{N_1}\space N_2 \space a_{N_2} \space ...\space N_k \space a_{N_k}\)
这里K代表多项式中非零项的数量,\(N_i\)和\(a_{N_i}\)(\(i\)=1,2,...,K)分别是指数(exponents)和系数(coefficients)。\(1\leq K\leq 10\),\(0\leq N_K<...< N_2<N_1\leq1000\).
输出要求
对于一个测试样例,你需要在一行以相同格式输出A和B的和。注意行尾没有多余的空格。请精确到小数点后一位。
样例输入
2 1 2.4 0 3.2
2 2 1.5 1 0.5
样例输出
3 2 1.5 1 2.9 0 3.2
分析:因为题上没有说是按照从大到小的顺序输入的,并且在我经过测试后也发现输入时指数的顺序是混乱的。 所以我一开始的想法是建两个链表,链表里每个节点都是都存储系数和指数,然后把链表排序后再相加。但一想到要写链表的排序算法我就放弃了,而且代码出错的概率太高了。
? 之后在看过大佬的们的题解后,发现可以用类似桶排序的方法做。就是先开一个比指数的上限还要大的数组,里面全都初始化成0,然后读取一对指数和系数,就把指数对应的项加上读取系数的值。之后先从小到大数一遍非0项的个数,再从大到小输出即可。时间复杂度是\(O_{(n)}\)。
? 废话不多说,直接上代码。
#include <stdio.h>
#define KMAX 1001
float cof[KMAX];
int main()
{
int k;
scanf("%d", &k);
int e; //e和c分别用来临时存储读取的指数和系数
float c;
for (int i = 0; i < k; i++)
{
scanf("%d%f", &e, &c);
cof[e] = c;
}
scanf("%d", &k);
for (int i = 0; i < k; i++)
{
scanf("%d%f", &e, &c);
cof[e] += c; //注意这里要用+=,因为A,B有相同的指数时,要加在一起
}
int cot = 0;
for (int i = 0; i < KMAX; i++) //先正序遍历一遍,计算项的个数
if (cof[i] != 0)
cot++;
printf("%d", cot);
for (int i = KMAX - 1; i >= 0; i--) //最后倒序输出
if (cof[i] != 0)
printf(" %d %.1f", i, cof[i]);
return 0;
}
原文链接:https://www.cnblogs.com/shenc9ea/p/12764828.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:2020年04月19日个人赛
下一篇:C++ 函数模板
- CodeForces Gym 100213F Counterfeit Money 2020-02-13
- 又是a+b 2019-09-08
- a+b的问题 2019-09-08
- 【BZOJ2693】jzptab(莫比乌斯反演) 2019-08-26
- 『ACM C++』 PTA 天梯赛练习集L1 | 027-028 2019-03-13
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash