tceic.com
简单学习网 让学习变简单
当前位置:首页 >> 学科竞赛 >>

两数之和解题报告


1、题目概括:假设有n(2<n<10)个数,给你n个数中每两个数的和(那么共有n(n-1)/2)个和,要你求n个非负整数。无解则输出Impossible。

2、题目分析:看这组数据
4(n)
500 210 100 120 400 300(n(n-1)/2)个

和)
先把这n(n-1)/2数排序。100 120 210 300 400 500
其中最小的和就应该是最小和第二小两个数之和。(这里枚举找最小和第二小两个数) 假设找到了 5 95(5+95=100)
再向下找,第二小的和就应该是最小和第三小数之和。 然后就可以找出三个和了。 继续找 115 那么就求出了三个和 100 120 210
接着找,依次的和就应该是最小和第i小数之和。 ....
最后如果找到n个数并且所有的和都用完就可以输出了。 ....

3、程序实现:关键有两点:1、找最小和第二小两个数。
2、判断枚举到的是否走过。
对于1 我用了while来找
对于2 我用了一个b数组,来判断本个数走过的次数(c数组记录初始走过的次数)
核心代码:
while(ans[1]+1<a[1]/2+1)//ans记录找到的结果
{
int s=0;//判断是否找到了一个不符合条件的数
ans[1]++;//第一个数
ans[2]=a[1]-ans[1];//第二个数应该是最小的和-第一个数(这里n(n-1)/2个和是a,已排好序)
m=2;//找到的结果的个数
for(int i=1;i<=n*(n-1)/2;i++) b[a[i]]=c[a[i]];//初始化b数组
for(int i=2;i<=n*(n-1)/2;i++)
if(b[a[i]]!=c[a[i]])//如果第i小的和没被用过
{
b[a[i]]--;//第i小的和用过一次
ans[++m]=a[i]-ans[1];//找到新一个结果,计数器加1
for(int j=2;j<m;j++)//枚举以前找到的数和刚刚找到的数做和
{
if(b[ans[m]+ans[j]]>0) b[ans[m]+ans[j]]--;//如果这个数还可以用,就把次数--
else {s=1;break;}//如果这个数不能用了,就记录不能用了,跳出循环
}
if(s==1) break;
if(m==n) shuchu();//如果找到n个数,就判断然后进行输出
}
}
4、总结归类 联想:这道题的n非常小,因为给出的和都小于100001,所以找到的数最大就是49999,所以我认为搜索也可以做到。(搜索就是找每个数)
但如果n非常大,就只可以用这个方法了。

推荐相关:

吴成瀚解题报告

吴成瀚解题报告_企业管理_经管营销_专业资料。运动会在编程课上, 老师给了我们...输入只有一行两个数(两数间用一个空格分隔), 第一个为整数, 表示机票原价, ...


2008noip提高组复赛题解

解题报告石家庄二中 李博杰 1.笨小猴【问题描述】 输入一个由小写字母构成的字符串,统计出现最多与最少字母的个数,若两数之差为质数, 输出“Lucky Word”和...


ACM各种题型解题报告

8页 免费 ACM解题报告4 2页 1下载券喜欢此文档...已知 N 个事件发生时刻和结束时刻(见下表,表中...每 行相邻两数之间用一个空格分隔。 Output 仅一...


统计学概论课后答案 第8章统计指数习题解答

价格(元) 报告期 45 450 要求: (1)计算该厂工业总产值指数及总产值增长额; (2)从相对数和 绝对数两方面对总产值变动进行因素分析; (3)用文字说明分析结果...


小学三年级奥数 数阵图一 知识点与习题

,而不知道两条直线上的三个 数之和都等于什么数...为了进一步学会掌握 这种解题方法,我们再看两例。 ...2014年细分行业研究报告年度盘点 2014年移动互联网O2O...


《花生采摘》解题报告

《花生采摘》解题报告_IT/计算机_专业资料。《花生采摘...将这些取出的数排序 后计算其花费(相邻两数的花费是...由于去摘花生必须从路边进入花生田和从花生田出来,...


奥​数​ ​ ​一 - 奥数 一

年龄问题、植树问题的解题方法; 3、灵活运用解题方法...【例题精讲】甲数是乙数的 10 倍,甲乙两数之和...2014年度细分行业报告汇集 2014年移动互联网O2O分析...


学习与解题口诀-初中数学七年级上册(北京师大版)

看成原点找 b 家,终点对应是和数。 同号两数...牢记口诀好解题,既快又准好帮手。 7.解一元一次...2014年度细分行业报告汇集 2014年移动互联网O2O分析...


重庆市小升初经典奥数题 附加解题思路和答案

重庆市小升初经典奥数题 附加解题思路和答案_六年级...5.已知 A、B 两数的最小公倍数是180,最大公约...2014年细分行业研究报告年度盘点 2014年移动互联网O2O...


...专题七 选择填空题解题策略 第二节 选择题的解题策...

C2 图像为 x 轴恒过定点 (?1,0) 两条...属于选择题 解题思路范畴,而是一种数形结合的解题...《政府工作 报告》 :“2001 年国内生产总值 达到 ...

网站首页 | 网站地图
All rights reserved Powered by 简单学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com