当前位置:首页 >> 学科竞赛 >>

两数之和解题报告


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非常大,就只可以用这个方法了。

相关文章:
解题报告
数的排列顺序无 关,所以我们可以令 a[I]...第2页 NOIp2002 普及组解题报告 湖南 黄艺海 总结: 四道题目其实都很容易,要想到正确可行的方法并不难,考察的是...
猜数解题报告
猜数解题报告广东中山纪念中学 陈启峰 【问题描述】佳佳和栋栋一起参加了在...(N,P,Q):其中 N 为 TNumber 类型,表示所猜数,P,Q 为两个整 形数。...
2014年鄞州小学程序设计复赛试题和解题报告
2014年鄞州小学程序设计复赛试题和解题报告_学科竞赛_...输出(a.out) 按题目要求输出 n 个数中最大数...Input(c.in) 两行 第一行:n m n 个不同...
解题报告 (11)
解题报告 (11)_计算机软件及应用_IT/计算机_专业资料。NOIP、NOI解题报告 ...程序要求:输入:n 和 m 如上例:输入:2 3 输出:正方形数与长方形个...
解题报告 (6)
解题报告 (6)_计算机软件及应用_IT/计算机_专业...为了让程序编写时思路清晰和利于调试,可以采取如下...(假设 x 为未知数,a,b,c,d 为系数) 则 x=(...
NOIP2014普及组解题报告
然后写写解题 报告∵这个报告主要是给初中同学看,所以我会写详细一点 Prolem 1 珠心算测试(count) 这道题其实很简单, 意思就是说给你一些数 a1,a2,a3,a...
解题报告 (13)
解题报告 (13)_计算机软件及应用_IT/计算机_专业资料。NOIP、NOI解题报告 ...通过 a0,a1,b0,b1 确定 X 中每项质因子最大幂数和最小幂数。然后 再把...
算法分析解题报告。
算法分析解题报告。_计算机软件及应用_IT/计算机_专业资料。算法分析结题报告 姓名...事实上,这是最长一条。 Input 输入第一行表示区域行数 R 和列数 C(...
ACM数论解题报告集合
ACM数论解题报告集合 隐藏>> Hdu 4143 y^2 = n +x^2 A Simple Problem ..., an,求数组中两个数的最小差值。即在数组中找 ai 和 aj , 使得 ai - ...
杭电ACM steps 2.2.1解题报告
杭电ACM steps 2.2.1解题报告_工学_高等教育_教育专区。杭电 ACM steps 2....第三数等于前两数之和,按照公 式 f[i]=f[i-1]+f[i-2]依次赋值即可,...
更多相关标签:
区间众数解题报告 | 数学解题报告 | 解题报告 | acm解题报告 | poj解题报告 | noip2016解题报告 | leetcode解题报告 | noip2015day2解题报告 |