注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Memento

这是一间记忆仓库~~

 
 
 

日志

 
 

陈题一枚  

2012-06-04 23:31:43|  分类: 乱搞 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
       给n个互不相同的整数{x1,x2,……,xn}。任取两个不同的数xi、xj有s=xi+xj,总共有n*(n-1)/2种取法,现在告诉你这n*(n-1)/2种取法的和s。求集合{x1,x2,……,xn}。
      
      解法:假设x1<x2<……<xn,首先对n*(n-1)/2个数排序S1<=S2<=……<=Sn*(n-1)/2,那么必然有最小的数S1=x1+x2,S2=x1+x3。这很容易证明,那么再考虑x1+x4、x1+x5、……、x1+xn和x2+x3总共n-2个数,他们必然对应着S3、S4、……、Sn,这也很容易就证明。那么我们枚举x2+x3对应的数为Si(3<=i<=n),通过S1=x1+x2、S2=x1+x3、Si=x2+x3解出x1、x2、x3,然后通过x1求出x4、……、xn,最后验证一下不等式x1<x2<……<xn,这样就可以求出原集合。总复杂度为O(n^3)。
  评论这张
 
阅读(48)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017